动态规划总结
动态规划算法的设计主要有以下４个步骤
(1) 描述最优解的结构
(2) 递归定义最优解的值
(3) 按自底向上的方式计算最优解的值
(4) 由计算出的结果构造一个最优解
其实最核心的步骤是 定义一个描述最优解的递归公式 (状态转移方程)
另外，适合采用动态规划方法求解最优化问题有三个特性：最优子结构、重叠子问题、无后效性
(1) 最优子结构: 问题的一个最优解中所包含的子问题的解也是最优的。总问题包含很多个子问题，而这些子问题的解也是最优的。
(2) 重叠子问题: 问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
(3) 无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
备忘录法：动态规划的一种变形，使用自顶向下的策略，更像递归算法。初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。实例可以参照矩阵链乘法部分。
状态转移方程
opt作为取最优值的函数（一般取min或max）, w(j, i)为一个实函数，其它变量都可以在常数时间计算出来
（１） 1D/1D
d[i] = opt{ d[j] + w(j, i) | 0 <= i < j } (1 <= i <= n)
（２） 2D/0D
d[i][j] = opt{ d[i-1][j] + xi, d[i][j-1] + yj, d[i-1][j-1] + zij } (1<= i, j <= n)
（３） 2D/1D
d[i][j] = w(i, j) + opt{ d[i][k-1] + d[k][j] }, (1 <= i < j <= n)
另外一种常用的2D/1D的方程为：
d[i][j] = opt{ d[i-1][k] + w(i, j, k) | k < j } (1<= i <= n, 1 <= j <= m)
（４） 2D/2D
d[i][j] = opt{ d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j}
常见于二维的迷宫问题，由于复杂度比较大，所以一般配合数据结构优化，如线段树、树状数组等。
常见题型
线性模型
线性模型的是动态规划中最常用的模型，上文讲到的最长单调子序列就是经典的线性模型，这里的线性指的是状态的排布是呈线性的
硬币找零
假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。
解法：
用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小硬币数。对于不同的硬币面值coin[0…n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], …)+1。对应于给定数目的找零total，需要求解sum[total]的值。
void find_coins( vector<int> coins，int total ){
int sum[total+1];
for(int i=1; i<=total; i++)
{
sum[i] = INT_MAX;
}
sum[0] = 0;
for(int i=1;i<=total;i++)
{
for(int j=0;j<coins.size();j++)
{
if( (i-coins[j])>=0 && sum[i] > sum[i- coins[j]]+1)
sum[i] = sum[i-coins[j]]+1;
}} }
扩展： 装配线调度（《算法导论》15.1），解法如下图所示
区间模型
区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。
最长公共子序列(Longest Common Subsequence,lcs)
对于序列S和T，求它们的最长公共子序列。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。求出一个即可。
解法：
对于X[1…m]和Y[1…n]，它们的任意一个lcs是Z[1…k]。
(1)如果X[m]=Y[n]，那么Z[k]=X[m]=Y[n],且Z[1…k-1]是X[1…m-1]和Y[1…n-1]的一个lcs；
(2)如果X[m]!=Y[n]，那么Z[k]!=X[m]时Z是X[1…m-1]和Y的一个lcs；
(3)如果X[m]!=Y[n]，那么Z[k]!=Y[n]时Z是X和Y[1…n-1]的一个lcs；
int max(int a, int b);
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));}
字符串相似度/编辑距离（edit distance）
对于序列S和T，它们之间距离定义为：对二者其一进行几次以下的操作(1)删去一个字符；(2)插入一个字符；(3)改变一个字符。每进行一次操作，计数增加1。将S和T变为同一个字符串的最小计数即为它们的距离。给出相应算法。
解法：
将S和T的长度分别记为len(S)和len(T)，并把S和T的距离记为m[len(S)][len(T)]，有以下几种情况：
如果末尾字符相同，那么m[len(S)][len(T)]=m[len(S)-1][len(T)-1]；
如果末尾字符不同，有以下处理方式:
修改S或T末尾字符使其与另一个一致来完成，m[len(S)][len(T)]=m[len(S)-1][len(T)-1]+1；
在S末尾插入T末尾的字符，比较S[1…len(S)]和S[1…len(T)-1]；
在T末尾插入S末尾的字符，比较S[1…len(S)-1]和S[1…len(T)]；
删除S末尾的字符，比较S[1…len(S)-1]和S[1…len(T)]；
删除T末尾的字符，比较S[1…len(S)]和S[1…len(T)-1]；
总结为，对于i>0,j>0的状态(i,j):
m[i][j] = min( m[i-1][j-1]+(s[i]==s[j])?0:1 , m[i-1][j]+1, m[i][j-1] +1)
这里的重叠子结构是S[1…i]，T[1…j]。
背包模型
(1)0/1背包
有N种物品（每种物品1件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。决策为第i个物品在前i-1个物品放置完毕后，是选择放还是不放，
状态转移方程为： f[i][v] = max{ f[i-1][v], f[i-1][v - Ci] +Wi } 时间复杂度O(VN)，空间复杂度O(VN) （空间复杂度可利用滚动数组进行优化达到O(V)，下文会介绍滚动数组优化）。
(2) 完全背包
有N种物品（每种物品无限件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。
状态转移方程为：
f[i][v] = max{ f[i-1][v - kCi] + kWi | 0 <= k <= v/Ci } (当k的取值为0,1时，这就是01背包的状态转移方程）
时间复杂度O( VNsum{V/Ci} )，空间复杂度在用滚动数组优化后可以达到O( V )。
进行优化后，状态转移方程变成：
f[i][v] = max{ f[i-1][v], f[i][v - Ci] +Wi }
时间复杂度降为O(VN)。
(3) 多重背包
有N种物品（每种物品Mi件）和一个容量为V的背包。放入第i种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。
状态转移方程
f[i][v] = max{ f[i-1][v - kCi] + kWi | 0 <= k <= Mi }
时间复杂度O( Vsum(Mi) )，空间复杂度仍然可以用滚动数组优化后可以达到O( V )。
优化：采用二进制拆分物品，将Mi个物品拆分成容量为1、2、4、8、… 2^k、Mi-( 2^(k+1) - 1 ) 个对应价值为Wi、2Wi、4Wi、8Wi、…、2^kWi、（Mi-( 2^(k+1) - 1 )）Wi的物品，然后采用01背包求解。这样做的时间复杂度降为O(Vsum(logMi) )。
状态压缩模型
状态压缩的动态规划，一般处理的是数据规模较小的问题，将状态压缩成k进制的整数，k取2时最为常见。
举例：对于一条n(n <= 11)个点的哈密尔顿路径C1C2…CN（经过每个点一次的路径）的值由三部分组成：
（１）每个顶点的权值Vi的和
（２）对于路径上相邻的任意两个顶点CiCi+1，累加权值乘积 Vi*Vi+1
（３）对于相邻的三个顶点CiCi+1Ci+2，如果Ci和Ci+2之间有边，那么累加权值三乘积 ViVi+1Vi+2
求值最大的哈密尔顿路径的权值 和 这样的路径的个数。
直接给出状态转移方程：
d[i][j][k] = max{ d[i ^ (1<<k)][t][j] + w(t, j, k) | (i & (1<<t)) != 0 }
树状模型
树形动态规划（树形DP），是指状态图是一棵树，状态转移也发生在树上，父结点的值通过所有子结点计算完毕后得出。
动态规划求解的一般思路
举例：给定一颗树，和树上每个结点的权值，求一颗非空子树，使得权和最大。
用d[1][i] 表示i这个结点选中的情况下，以i为根的子树的权和最大值;
用d[0][i]表示i这个结点不选中的情况下，以i为根的子树的权和最大值;
d[1][i] = v[i] + sum{ d[1][v] | v是i的直接子结点 && d[1][v] > 0 }
d[0][i] = max( 0, max{ max( d[0][v], d[1][v] ) | v是i的直接子结点 } )
这样，构造一个以1为根结点的树，然后就可以通过dfs求解了。