黑白图像存储
像素点灰度值 : 0----255 ，为8 位二进制数
图像的灰度值序列 : { p 1 , p 2 , … , p n } ，p i=[0,255]为第i 个像素点灰度值
图像存储：每个像素的灰度值占8 位，有n个灰度值，所以总计空间为 8n
但是如果是白点，占用空间实质上很少(有很多个0)，所以实质上可以用较小的存储空间存储
改进：同一段的像素占用位数相同，不同段可以不同
我们将灰度值序列分为m个段，对于每段，由两部分组成=段头+元素
段头：记录l[t](8 位) 和b[t](3 位) 需要11位
元素：第t段有l[t]个像素，每个占用 b[t]位 一共需要l[t]*b[t]
总位数为b[1]*l[1]+b[2]*l[2]+… +b[m]*l[m]+11m
递推方程：
注意，对于S[i]，只用讨论分成前后两部分即可。因为S[1----i-1]已经有最优划分，所以S[i]只是比S[i-1]多插入一个末尾元素，只会影响以他为尾的[x-----i]的序列，所以只用讨论将[x----i]序列单独列为一部分。
时间复杂度：O(n)
检索二叉树
定义：首先定义每个结点以及结点间隙的搜索概率
用此构建一颗数，计算器平均查找长度
给定数据集
S = < x 1 , x 2 , …, x n >, S 的存取概率分布如下：P = < a 0 , b 1 , a 1 , b 2 , a 2 , … , b n , a n >
的求一棵最优的 即平均比较次数最的少的 ) 二分检索树.
符号定义：
S<A,E>= < 0.04, 0.1, 0.02, 0.3, 0.02, 0.1,
0.05, 0.2, 0.06, 0.1, 0.01>
也可以符号化定义S= <a0, b1 , a1 , b2 , a2 , … , bn , an >
P【i,j】:i-j节点之间所有的节点概率和间隙概率
P[2,4]=<0.02,0.3,0.02,0.1,0.05,0.2,0.06>
w[i,j]:i-j节点之间所有的节点概率和间隙概率之和
w[2,4]=(0.3+0.1+0.2)+(0.02+0.02+0.05+0.06)= 0.75
m[i,j] 是相对于输入 S[i,j] 最优二叉搜索树的平均比较次数
所以由递推方程：
可以看出，解答方法类似于解矩阵链，都是可以用递归或者迭代进行。只不过递归存在重复运算，所以采用迭代的方法。
首先有初值
m(1,1)=0.16
m(2,2)=0.34
m(3,3)=0.17
m(4,4)=0.31
m(5,5)=0.17
之后求m(1,2)m(2,3)m(3,4)m(4,5)
比如m(1,2)=min{m(1,0)+m(2,2)，m(1,1)+m(2,1)}+0.48=0.64
之后的类似方法求。
i, j 的所有组合O(n 2 )种 种
每种要对不同的 k 进行计算，k=O(n)
每次计算为常数时间
时间复杂性： T (n) = O (n 3 )
空间复杂度： S (n) = O (n 2 )
生物建模
给出了一组生物方面的定义，实质建模后为
转化为数学模型
得到的递归方程：
解析：其实也类似于矩阵链的问题，对于C[i,j]，对比参考的是C[i,j-1]。相当于多了一个j节点。则这个j节点可以什么链都不构建C[i,j]=C[i,j-1]。也可以与i<=k<=j-4的k节点构建成链，此时则转为如图方程
时间复杂度：
子问题个数： i, j 有 对的组合有 O (n 2 ) 个
对于给定的 i 和 j ，j 需要考察与所有可
能的 k 中 是否匹配，其中 i <= k <=j-4 ，需要 O (n) 时间.是算法时间复杂度是O(n^3).
序列的编辑距离
给定两个序列 S 1 和 和 S 2 ，通过一系列字符编辑（插入、删除、替换等）操作，将S1转变成S2 .完成这种转换所需要的最少的编辑操作个数称为S1和S2的编辑距离.
举个例子：
一定注意，边界情况C[0,j]=j C[i,0]=i。意思为执行j或者i编辑
而对于C[i,j]其实是不考虑长度等关系的，而是向C[0,j]或者C[i,0]方向移动。只不过说要让值最小【可能说的不清楚，慢慢理解】
举个例子：对vi和wi
首先C[0,1]=1C[0,2]=2 C[1,0]=1C[2,0]=2
接下来对于C[1,1]因为v!=w 所以由三条路可以走，取值最小的即可
子问题由 i, j 界定，
有O (m n) 个子问题
• 每个子问题的计算为常数时间
• 算法的时间复杂度是O (nm)