[数据结构与算法]动态规划的小总结

一 ，首先动态规划算法的步骤：

1先刻画最优解的结构

2递归定义最优解的值

3按自底向上的方式计算最优解的值

4根据计算最优解的值时得到的信息构造最优解

用一个表来记录已解决的子问题的答案，不管这个子问题是否以后会被用到，计算过就填入表中，这是动态规划的基本思想。

二，再是几种经典的模型

1.矩阵连乘问题：

d[i][j]表示在区间[i,j]上的最优计算次数，加括号的位置不同。

状态转移方程：d[i][j]?=?min{?d[i][k],?d[k+1][j] }+p[i-1]p[k]p[j] ? ? ? ?? i<=k<j;i<j

????????????????????????????????? =0?????????????? i=j

2.? 0-1背包问题：
特点：有N种物品和一个容量为j的背包，每种物品只有一件，可以选择放或者不放。
状态转移方程：F[i，j]=max{F[i-1，j]，F[i-1,j-c[i]+w[i]}???? j>=w[i]

????????????????????????????????????? =F[i,-1j]?? j<w[? i]

3.图像压缩问题

压缩的原理就是把序列{p1,p1,……pn}进行设断点，将其分割成一段一段的。分段的过程就是要找出断点，让一段里面的像素的最大灰度值比较小，那么这一段像素(本来需要8位)就可以用较少的位(比如7位)来表示，从而减少存储空间。图像压缩问题就是要确定像素序列{p1,p1,……pn}的最优分段，使得依此分段所需的存储空间最小。

设l[i],b[i],1<=i<=m是{p1,p1,……pn}的一个最优分段，则l[1],b[1]是{p1,……,pl[1]}的一个最优分段，且l[i],b[i],2<=i<=m是{pl[1]+1,……,pn}的一个最优分段。即图像压缩问题满足最优子结构性质。
设s[i],1<=i<=n是像素序列{p1,p1,……pi}的最优分段所需的存储位数，则s[i]为前i-k个的存储位数加上后k个的存储空间。由最优子结构性质可得：

s[i]=min{s[i-k]+k*bmax(i-k+1,i}+1l 1≤k≤min{i,256}其中bmax(i,j)=| log(max{px}+1)

4.最优二叉搜索树的问题
给定关键字ki,...,kj，假设kr(i<=r<=j)是包含这些键的一棵最优子树的根。其左子树包含关键字ki,...,kr-1和虚拟键di-1,...,dr-1，右子树包含关键字kr+1,...,kj和虚拟键dr,...dj。我们检查所有的候选根kr,就保证可以找到一棵最优二叉查找树。
定义e[i,j]为包含关键字ki,...,kj的最优二叉查找树的期望代价，最终要计算的是e[1,n]。
当j?=?i?-?1时，此时子树中只有虚拟键，期望搜索代价为e[i,i?-?1]?=?qi-1.
当j?>=?i时，需要从ki,...,kj中选择一个根kr，然后分别构造其左子树和右子树。下面需要计算以kr为根的树的期望搜索代价。然后选择导致最小期望搜索代价的kr做根。
现在需要考虑的是，当一棵树成为一个节点的子树时，期望搜索代价怎么变化？子树中每个节点深度都增加1.期望搜索代价增加量为子树中所有概率的总和。
对一棵关键字ki,...,kj的子树，定义其概率综合为:

w(i, j)=p[l](l=i到j)+q[l](l=i-1到j)

所以最终的递推公式为：

eli,j]= min{e[i,r-1]+e[r+ 1,j]+ w(i,j)} if? i<= j;i<=r<=j

????? =q[i-1]?????????? j=i-1