1. 动态规划思想
1.将待求解问题分解成若干子问题，先求解子问题，再结合这些子问题的解得到原问题的解。与分治法不同，适合用动态规划求解的问题经分解得到的子问题往往不是互相独立的。
2.性质
（1）最优子结构性质
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。在分析该问题的最优子结构性质时，所用的方法具有普遍性。首先假设由问题的最优解导出的其子问题的解不是最优的，再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
（2）子问题重叠问题
在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算。动态规划算法正是利用了这种子问题的重叠性质，对每个子问题只解一次， 然后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
3.步骤设计
- 找出最优解的性质，并刻画其结构特征。
- 递归地定义最优值。
- 以自底向上的方式计算最优值。
- 根据计算最优值时得到的信息，构造最优解。
2. 备忘录方法
1.备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
2.备忘录方法为每个子问题建立一一个记录项，初始化时，该记录项存入个特殊的值， 表示该子问题尚未求解。在求解过程中，对每个待求的子问题，首先查看其相应的记录项。若记录项中存储的是初始化时存入的特殊值，则表示该子问题是第一次遇到， 此时计算出该子问题的解，并保存在其相应的记录项中，以备以后查看。若记录项中存储的已不是初始化时存入的特殊值，则表示该子问题已被计算过，其相应的记录项中存储的是该子问题的解答。
3. 备忘录和动态规划
- 当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算。
- 当子问题空间中的部分子问题可不必求解时，用备忘录方法则较有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。
3. 动态规划实例
矩阵连乘问题
1. 问题描述
给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1，2…，n-1。矩阵乘法满足结合律，如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘积次数最少。(矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数，若A是一个pq的矩阵，B是一个qr的矩阵，则需要数乘次数为p*q*r)
2. 分析最优解结构
计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。
- 证明其最优子结构：
反证法：如果计算A[1:k]的次序需要的计算量更少，则用此次序替换原来计算A[1:k]的次序，得到的计算A[1:n]的计算量将比最优次序所需计算量更少，矛盾。同理可得，计算A[1:n]的最优次序包含计算矩阵子链A[k+1:n]的次序也是最优的。
3. 建立递归关系（Ai的维度是pi-1*pi）
4. 计算最优值
m[i][j]的断开位置k记为s[i][j],在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。在下面给出的动态规划算法MatrixChain中，输入参数{po,p1,…, pn}存储于数组p中。除了输出最优值数组m,算法还输出记录最优断开位置的数组S。
void matrixChain(int *p,int n,int **m,int **s)
{
for(int i=1;i<=n;i++) m[i][i]=0;
for(int r=2;r<=n;r++)//对角线循环
{
for(int i=1;i<=n-r+1;i++) //行循环
{
int j=r+i-1;//列的控制
m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;k<j;k++) //k从i+1到j-1循环找m[i][j]的最小值
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
5. 构造最优解
void Traceback(int i,int j,int **s)
{
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<','<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<','<<j<<endl;
}
6. 复杂度分析
- 时间复杂度为
O(n^3)， - 空间复杂度为
O(n^2)。
最长公共子序列
1. 问题描述
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
2. 最优公共子序列的结构
最优子结构性质
反证法：
（1）若Zk不等于Xm,则{Z1,Z2,…,Zk,Xm}是X和Y的长度为k+1的公共子序列。这与z是X和Y的最长公共子序列矛盾，所以Zk=Xm=Ym。Zk-1是Xm-1和Yn-1的最长公共子序列。若Xm-1和Yn-1有长度大于k-1的公共子序列W,则将Xm加在其尾部产生X和Y的长度大于k的公共子序列。此为矛盾。所以，Zk-1是Xm-1和Yn-1的最长公共子序列。
（2）若Xm-1和Y有长度大于k的公共子序列W,则W也是X和Y的长度大于k的公共子序列。这与Z是X和Y的最长公共子序列矛盾。
（3）的证明类似
由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。
3. 子问题的递归结构
- 当Xm=Yn时找出Xm1和Yn-1的最长公共子序列，然后在其尾部Xm (Xm=Yn)
- 当Xm不等于Yn，找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列，这两个公共子序列中较长者即为X和Y的最长公共子序列。
用c[i][j]记录序列X和Y的最长公共子序列的长度，x={x1,x2,...,xi); Y={y1,y2,...,yj}。 当i=0或j=0时，空序列是X和Y的最长公共子序列,c[i][j]=0。
4. 计算最优值
计算最长公共子序列长度的动态规划算法LCSLength以序列X={x1, x2, … xm}和Y={y1,Y2, . yn}作为输入，输出两个数组c和b。其中，c[i][j]存储X和Y的最长公共子序列的长度，b[i][j]记录c[i][j]的值是由哪个子问题的解得到的，这在构造最长公共子序列时要用到。问题的最优值，即X和Y的最长公共子序列的长度记录于c[m][n]中。
void LCSLength(int m,int n,char *x,char *y,int **c,int **b)
{
int i,j;
for(i=1;i<=m;i++) c[i][0]=0;
for(i=1;i<=n;i++) c[0][i]=0;
for(i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(x[i]==y[j])
{c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}
else if(c[i-1][j]>=c[i][j-1])
{c[i][j]=c[i-1][j];b[i][j]=2;}
else
{c[i][j]=c[i][j-1];b[i][j]=3;}
}
}
}
代码时间复杂度为O(mn)
5. 例子
- X={A,B,C,B,D,A,B},M=7;
- Y={B,D,C,A,B,A} ,N=6;
6.构造最长公共子序列
LCS(m,n,x,b)可以打印序列X和Y的最长公共子序列，LCS代码时间复杂度为O(m+n)
void LCS(int i，int j，char *x，int **b)
//LCS根据b的内容打印出Xi和Yj的最长公共子序列
{
if (i ==0 || j==0) return;
if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; }
else if (b[i][j]== 2) LCS(i-1，j，x，b);
else LCS(i，j-1，x，b);
}
7.改进
- 在算法LcsLength和lcs中，可进一步将数组b省去。事实上，数组元素
c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在O(1)时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。 - 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至
O(min{m,n})。
凸多边形最优三角部分
1.问题描述
用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。
若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。
多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。
给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。
2.最优子结构性质
若凸(n+1)边形P={v0,v1,…,vn-1}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。
3.最优三角剖分的递归结构
定义t[i][j]，1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1。
4.计算最优值
下面描述的计算凸n+1边形P={v0, V1, … vn}的最优三角剖分的动态规划算MinWeightTriangulation。
template<class Туре>
void MinWeightTriangulation(int n, Type **t, int **s)
{
for(int i=1; i <= n; i++) t[i][i] = 0;
for (int r=2; r <= n; r++)
{
for (int i=1; i <= n-r+1; i++)
{
int j=i+r-1;
t[i][j] = t[i+1][j] + W(i-1, i, j);
s[i][j] = i;
for (int k=i+1; k<j; k++)
{
int u = t[i][k]+t[k+1][j]+W(i-1, k, j);
if (u<t[i][j]) {t[i][j] = u;s[i][j] = k;}
}
}
}
}
复杂度分析:
- 时间复杂度为
O(n^3) - 空间复杂度为
O(n^2)。
最大子段和
1.问题描述
给定由n个整数(可能为负整数)组成的序列a1,a2, ..., an,求该序列的连续子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。例如，当(a1, a2,a3, a4,a5, a6)=( -2, 11,-4,13,-5, -2)时，最大子段和为之a2+a3+a4=20。
2.动态规划算法
所以其递归式为 b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n
3.算法描述
int MaxSum(int n,int *a)
{
int sum=0,b=0;
for(int i=1;i<=n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}
4.时间复杂度分析
需要O(n)的计算时间和O(n)空间
0-1背包问题
1.问题描述
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
2.递归关系
以上递推式是书本的内容，如图所示是下列代码的递推式，W就是C，可选择物品是0…i
3.算法描述
int KnapSack(int n,int w[],int v[],int x[],int C)
{
int i,j;
for(i=0; i<=n; i++) m[i][0]=0;
for(j=0; j<=C; j++) m[0][j]=0;
for(i=1; i<=n; i++)
{
for(j=1; j<=C; j++)
{
if(j<w[i]) m[i][j]=m[i-1][j];
else m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
}
}
j=C;
for(i=n; i>=1; i--)
{
if(m[i][j]>m[i-1][j]) {x[i]=1; j=j-w[i];}
}
return m[n][C];
}
4.示例
5.时间复杂度分析
从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2^n时，算法需要Ω(n^2n)计算时间。