原书《算法导论》第4章
动态规划和分治方法的区别
动态规划与分治方法相似，都是通过组合子问题的解来求解原问题。
分之方法将问题分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。子问题的求解是递归进行的，递归会将其划分为更小的子子问题。在这种情况下，分治算法会做许多不必要的工作，它会反复求解那些公共子子问题。
与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。动态规划算法对每个子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。
4个步骤设计动态规划
动态规划通常用来求解最优化问题optimization problem。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的一个最优解（an optimal solution），而不是最优解（the optimal solution），因为可能有多个解都达到最优值。
我们通常按如下4个步骤来设计一个动态规划算法：
1、刻画一个最优解的结构特征；
2、递归地定义最优解的值；
3、计算最优解的值，通常采用自底向上的方法；
4、利用计算出的信息构造一个最优解
步骤1-3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤4。如果确实要做步骤4，有时就需要在执行步骤3的过程中维护一些额外信息，以便用来构造一个最优解。
1、钢条切割
案例的推导过程详见课本。
钢条的最优切割收益：
r(n) = max(p(n), r(1)+r(n-1), ....r(n-1)+r(1))
上述的问题公式，符合最优子结构。
最优子结构（optimal substruction）：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
简化上述问题公式：
r(n) = max(p(n), r(1)+r(n-1), ....r(n-1)+r(1))
r(n) = max(p(n)+r(0), r(1)+r(n-1), ....r(n-1)+r(1))
r(n) = max(p(n)+r(0), p(1)+r(n-1), ....p(n-1)+r(1))
r(n) = max(p(i)+r(n-i)), 1<=i<=n
简化后，公式中只包含一个相关子问题的解，而其子问题包含自身的一个相关子问题。这样就已经可以通过递归（分治算法）实现。
在如下的输入中使用递归实现公式时，重复计算会让时间爆炸性增长。
使用动态规划，和递归的本质区别，就是对中间结果做保存。这样，减少掉重复计算。
下方两种动态规划的方法有相同的渐近运行时间，自底向上由于没有频繁调用递归所以具有更小的系数。但某些情况下自顶向下方法不会计算所有子问题的解。
1、带备忘的自顶向下方法：仍然按照递归编写，但是计算过程中会保留每一个子问题的解。当需要一个子问题的解时，首先检查是否已经保存过。如果是，则直接返回保存的值。
2、自底向上方法：我们可以将子问题按规模排序，按由小到大的顺序计算，直到得到目标解。当求解某个子问题时，它所依赖的更小的子问题都已经求解完毕，结果已经保存。
实现
public class cutRod {
public static void main(String args[]) {
int[] lengthOfRod = new int[]{0,1,2,3,4,5,6,7,8,9,10};
int[] priceByLen = new int[]{0,1,5,8,9,10,17,17,20,24,30};
// r(n)= max(pi+r(n-i))
int maxProfit = bottom_up_cutRod(priceByLen,7);
}
// 递归计算
private static int cutRod(int[] priceByLen, int lengthOfR) {
if (lengthOfR==0) {
return 0;
}
int profitInTotal = Integer.MIN_VALUE;
for (int i=1; i<=lengthOfR; i++) {
profitInTotal =
Math.max(profitInTotal,(priceByLen[i]+cutRod(priceByLen,lengthOfR-i)));
}
return profitInTotal;
}
// 自上而下的动态规划
// 对计算过程中的每个结果进行保存，防止重复计算
private static int memorized_cutRod(int[] priceByLen, int lengthOfR) {
int[] memorizedRes = new int[lengthOfR+1];
for (int i=0; i<=lengthOfR; i++) {
memorizedRes[i] = Integer.MIN_VALUE;
}
return memorized_cutRod_aux(priceByLen,lengthOfR,memorizedRes);
}
// 自上而下的计算还是递归，但是对每个结果做了保存
private static int memorized_cutRod_aux(int[] priceByLen, int lengthOfR, int[] memorizedRes) {
if (memorizedRes[lengthOfR]>=0) {
return memorizedRes[lengthOfR];
}
int profitInTotal = Integer.MIN_VALUE;
if (lengthOfR==0) {
profitInTotal = 0;
} else {
for (int i=1; i<=lengthOfR; i++) {
profitInTotal =
Math.max(profitInTotal,priceByLen[i]+memorized_cutRod_aux(priceByLen,lengthOfR-i,memorizedRes));
}
}
memorizedRes[lengthOfR] = profitInTotal;
return profitInTotal;
}
// 自下而上的动态规划
private static int bottom_up_cutRod(int[] priceByLen, int lengthOfR) {
int[] memorizedRes = new int[lengthOfR+1];
memorizedRes[0] = 0;
for (int j=1; j<=lengthOfR; j++) {
int profitInTotal = Integer.MIN_VALUE;
for (int i=1; i<=j; i++) {
profitInTotal = Math.max(profitInTotal,priceByLen[i]+memorizedRes[j-i]);
}
memorizedRes[j] = profitInTotal;
}
return memorizedRes[lengthOfR];
}
// 扩展自下而上的动态规划，记录钢条切割方案
private static int[][] extended_bottom_up_cutRod(int[] priceByLen, int lengthOfR) {
// [i][0]记录最优解，[i][1]记录最优解对应切割方案
int[][] memorizedRes = new int[lengthOfR+1][2];
for (int j=1; j<=lengthOfR; j++) {
int profitInTotal = Integer.MIN_VALUE;
for (int i=1; i<=j; i++) {
if (profitInTotal<(priceByLen[i]+memorizedRes[j-i][0])) {
profitInTotal = priceByLen[i]+memorizedRes[j-i][0];
memorizedRes[j][1] = i;
}
}
memorizedRes[j][0] = profitInTotal;
}
return memorizedRes;
}
private void print_cutRod_Solution(int[] priceByLen, int lengthOfR) {
int[][] res = extended_bottom_up_cutRod(priceByLen,lengthOfR);
int n = lengthOfR;
while(n>0) {
System.out.println(res[n][1]);
n = n-res[n][1];
}
}
}
2、矩阵链乘法-没看懂
矩阵相乘demo
MATRIX_MULTIPLY(A,B)
if A.columns!=B.rows
error "incompatible dimensions"
else let C be a new A.rowsXB.columns matrix
for i=1 to A.rows
for j=1 to B.columns
cij=0;
for k=1 to A.columns
cij=cij+aik*bkj
return C两个矩阵A和B只有相容，即A的列数等于B的行数时，才能相乘。如果A是pxq的矩阵，B是qxr的矩阵，那么乘积C是pxr的矩阵。
以矩阵链<A1,A2,A3>为例，假设三个矩阵规模分别是10x100,100x5,5x50。如果按照((A1A2)A3)的顺序计算，计算量是7500次标量乘法。如果按照((A1(A2A3))的顺序计算，计算量是75000次标量乘法。第一种比第二种快10倍。
矩阵链乘法问题（matrix-chain multiplication problem）可描述如下：给定n个矩阵的链<A1,A2...An>，矩阵Ai的规模为p(i-1)xp(i)(1<=i<=n)，求完全括号化方案，使得计算乘积A1A2....An所需标量乘法次数最少。
求解矩阵链乘法问题并不是要真正进行矩阵相乘运算，我们的目标只是确定代价最低的计算顺序。
计算括号化方案的数量
P(n) = 1，如果n=1; P(n)=sum(P(k)*P(n-k))，如果n>=2.
使用动态规划解决矩阵链乘法
步骤1：最优括号化方案的结构特征
在原问题AiAi+1...Aj的最优括号化方案中，对子链Ak+1Ak+2...Aj进行括号化的方法，就是自身的最优括号化方案。
步骤2：一个递归求解方案
m[i,j] =0, 如果i=j; = min{m[i,j] = m[i,k]+m[k+1,j]+pi-1pkpj}，如果i<j.
步骤3：计算最优代价
没看懂。。。。。。。。。。。。。
实现
n=p.length-1
let m[1...n,1...n]and s[1...n-1,2...n]be new tables
for i=1 to n
m[i,i]=0
for l=2 to n
for i=1 to n-l+1
j=i+l-1
m[i,j]=MAX_VALUE
for k=i to j-1
q=m[i,k]+m[k+1,j]+p(i-1)pkpj
if q<m[i,j]
m[i,j] = q
s[i,j] = k
return m and s步骤4：构造最优解
没看懂。。。。。。。。。。
3、动态规划原理
在本节中，我们关注适合应用动态规划方法求解的最优化问题应该具备的两个要素：最优子结构和子问题重叠。同时，更深入地讨论在自顶向下方法中如何借助备忘机制来充分利用子问题重叠特性。
最优子结构
如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。
发现最优子结构性质的过程：
1）证明问题最优解的第一个组成部分是做出一个选择，例如，选择钢条第一次切割位置，选择矩阵链的划分位置等。做出这次选择会产生一个或多个待解的子问题。
2）对于一个给定问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。
3）给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。
4）利用cut-and-paste反证：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。
重叠子问题
如果原问题使用递归算法，当递归反复求解相同的子问题，我们就称最优化问题具有重叠子问题overlapping subproblems性质。
动态规划算法通常对每个子问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表为常量时间。
递归调用的时间复杂度是O(2^n).
通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快（都是O(n^3)，相差一个常量），因为自底向上的算法没有递归调用的开销，表的维护开销也更小。
4、最长公共子序列
给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn}，求X和Y长度最长的公共子序列。公共子序列的每个元素都要按序在X和Y中出现，但是在X和Y中的下标可以不同。
步骤1：刻画最长公共子序列的特征
LCS的最优子结构：令X={x1,x2,x3...xm}和Y={y1,y2,y3...yn}为两个序列，Z={z1,z2,...zk}为X和Y的任意LCS。
1）如果xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS；
2）如果xm !=yn，则zk !=xm且Z是Xm-1和Y的一个LCS；
3）如果xm !=yn，则zk !=yn且Z是X和Yn-1的一个LCS；
也就是，两个序列的LCS包含两个序列的前缀的LCS。因此，LCS问题具有最优子结构性质。
步骤2：一个递归解
当xm !=yn，为了求X和Y的一个LCS，可能需要求X和Yn-1的一个LCS及Xm-1和Y的一个LCS。但是这几个子问题都包含求解Xm-1和Yn-1的LCS的子子问题。很多其他问题也共享子子问题。
定义c[i,j]表示Xi和Yj的LCS的长度，LCS的公式如下。
c[i,j] =
-
0, 若i=0或j=0
-
c[i-1,j-1]+1, 若i,j>0且xi=yj
-
max(c[i,j-1],c[i-1,j]), 若i,j>0且xi!=yj
步骤3：计算LCS的长度
基于步骤2的公式，实现代码：
LCS_LENGTH(X,Y) {
m=X.length;
n= Y.length;
let b[1...m,1...n] and c[0...m,0...n]be new tables
for i=1 to m
c[i,0]=0
for j=0 to n
c[0,j]=0
for i=1 to m
for j=1 to n
if xi==yj
c[i,j]=c[i-1,j-1]+1
b[i,j]="upLeft"
else if c[i-1,j]>=c[i,j-1]
c[i,j]=c[i-1,j]
b[i,j]="up"
else
c[i,j]=c[i,j-1]
b[i,j]="left"
return c and b
}参考如下解释：
步骤4：构造LCS
在步骤3返回的表b、c中反序打印字符即可。
PRINT-LCS(b,X,i,j) {
if i==0 or j==0
return;
if b[i,j]=="upLeft"
PRINT-LCS(b,X,i-1,j-1)
print xi
else if b[i,j]=="up"
PRINT-LCS(b,X,i-1,j)
else
PRINT-LCS(b,X,i,j-1)
}**
