动态规划简介
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于动态规划算法求解的问题，经分解的得到的子问题往往不是相互独立的。分治算法两个自问题一般是不重叠的。
若用分治法来解这类问题，则分解的得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。在用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保存已解决子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算。
自顶向下计算会产生重复计算的问题。比如要计算下图中要计算a[i,j]为塔顶的子塔所能获得的最大路径和。那么每走一层都要问下一层它走过最长的路径是啥，红框部分重叠就是为重复部分，那么这部分就被至少问了2次以上。
动态规划应用
1. 计算最长公共子序列长度
计算最长公共子序列长度的动态规划算法LCSLength以序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}作为输入，计算得到数组c，其中c[i][j]存储序列Xi={x1,x2,...,xi}和序列Yj={y1,y2,...,yj}的最长公共子序列长度。
解题思路
设A="a[0]...a[m]"，B="b[0]...b[n]"，并且Z="z[0]...z[k]"为它们最长公共子序列。在找A、B公共子序列时，若a[m]=b[n]，则进一步解决一个子问题：找"a[0]...a[m-1]"和"b[0]...b[n-1]"的最长公共子序列。若a[m]≠b[n]，则要解决两个子问题：找"a[0]...a[m-1]"和"b[0]...b[n]"的最长公共子序列和找"a[0]...a[m]"和"b[0]...b[n-1]"的最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
但LCSLength存在子问题重叠性质，如在计算X和Y的LCSLength时，可能要计算X和Y[n-1]及X[m-1]和Y的LCSLength，而这两个子问题都包含了一个公共子问题，即计算X[m-1]和Y[n-1]的最长公共子序列。所以用c[i][j]记录Xi和Yj的最长公共子序列的长度。当i=0或j=0时，空序列时Xi和Yj的最长公共子序列。故此时c[i][j]=0.其他情况下，由最优子结构性质可建立递归关系如下：
代码
void LSCLength(int m,int n,char *x,char *y,int **c){
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(j=1;j<=n;i++)
{
if(x[i]==y[j]) { c[i][j] = c[i-1][j-1]+1; }
else if(c[i-1][j] >= c[i][j-1]) c[i][j]=c[i-1][j]
else { c[i][j]=c[i][j-1]; }
}
}
时间复杂度
由于每个数组单元的计算耗时为O(1)时间，算法LCSLength耗时O(mn)。
2. 0-1背包问题
0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应该如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？
选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题成为0-1背包问题。
最优子结构性质
此问题的形式化描述是：给定C>0，wi>0，vi>0，1<=i<=n，要求找出一个n元0-1向量(x1，x2，...，xn)，xi∈{0，1}，1<=i<=n，使得∑(i=1n)wixi<=C，而且∑(i=1n)vixi达到最大。
设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解：
证明：使用反证法。若不然，设(z2,z3,…,zn)是上述子问题的一个最优解，而(y2,y3,…,yn)不是它的最优解。显然有
∑vizi > ∑viyi (i=2,…,n)
且 w1y1+ ∑wizi<= c
因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)
说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解——>导出(y1,y2,…,yn)不是背包问题的最优解（因为大前提已经是(y1,y2,…,yn)是 (3.4.1)的一个最优解，而现在又导出一个(y1,z2, z3,…,zn)是(3.4.1)的最优解，所以是前后矛盾的），矛盾。
解题思路
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
首先要明确这张表是至底向上，从左到右生成的。为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。
同理，c2=0，b2=3,a2=6。对于承重为8的背包，a8=15,是怎么得出的呢？根据01背包的状态转换方程，需要考察两个值，一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi。
在这里， f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值。f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值。f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6。由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包。
设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i,j)是背包容量为j，可选择物品物品为i，i+1，...，n时0-1背包问题的最优值。有0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：
在max{m(i+1,j),m(i+1,j-wi)+vi}中，m(i+1,j)代表不选当前物品，而m(i+1,j-wi)+vi代表选择当前物品（加上当前物品价值）。如果当前物品重量比背包总容量还打的话，那就只能是m(i+1,j)。
代码
当wi（1<=i<=n）为正整数时，用二维数组m[][]来存储m(i,j)的相应值，可设计解0-1背包问题的动态规划算法 Knapsack如下：
//n为物品个数，c为背包容量
void Knapsack(Type v, int w , int c , int n , Type **m)
{
int jMax = min(w[n]-1,c); //比较背包容量和当前物品的重量
/**先初始化下标最大（n）的**/
//初始化背包容量从0到jMax的最优值
for(int j=0; j<=jMax; j++) m[n][j] = 0;
//初始化背包容量>=当前物品重量时m[n][j]的值（若背包容量<当前物品则保留为0）
for(int j=w[n]; j<=c; j++) m[n][j] = v[n];
/**计算下标比n小的**/
for(int i = n-1; i>1 ; i--){
jMax = min(w[i]-1,c);
//没选之前，m[i][j]皆为前面选的价值总和
for(int j=0; j<=jMax; j++) m[i][j] = m[i+1][j];
//j从放得下本物品开始的容量开始
for(int j=w[i]; j<=c; j++) m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c] = m[2][c];
if(c>=w[1]) m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
}
//构造相应的最优解
void Traceback(Type **m, int w , int c, int n, int x)
{
for(int i=1;i<=n;i++)
if(m[i][c]==m[i+1][c]) x[i] = 0;
else { x[i] = 1;c-=w[i]; }
x[n] = (m[n][c])?1:0;
}
算法Knapsack计算后，m[1][c]给出所要求的0-1背包问题的最优值。相应的最优解可由算法Traceback计算如下。如果m[1][c]=m[2][c]，则x1=0，否则x1=1。当x1=0时，由m[2][c]继续构造最优解。
