常见的动态规划问题分析与求解
动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一，并不像回溯法具有解决绝大多数问题的银弹（全面解析回溯法：算法框架与问题求解)。为了解决动态规划问题，只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集，希望能有所帮助。难度评级受个人主观影响较大，仅供参考。
目录（点击跳转）
动态规划求解的一般思路
备忘录法
1.硬币找零
扩展1：单路取苹果
扩展2：装配线调度
2.字符串相似度/编辑距离（edit distance）
应用1：子串匹配
应用2：最长公共子序列
3.最长公共子序列(Longest Common Subsequence,lcs)
扩展1：输出所有lcs
扩展2：通过LCS获得最长递增自子序列
4.最长递增子序列（Longest Increasing Subsequence,lis）
扩展：求解lis的加速
5.最大连续子序列和/积
扩展1：正浮点数数组求最大连续子序列积
扩展2：任意浮点数数组求最大连续子序列积
6.矩阵链乘法
扩展：矩阵链乘法的备忘录解法（伪码）
7.0-1背包问题
8.有代价的最短路径
9.瓷砖覆盖（状态压缩DP）
10.工作量划分
11.三路取苹果
参考资料
附录1：其他的一些动态规划问题与解答（链接）
附录2：《算法设计手册》第八章 动态规划 面试题解答
动态规划求解的一般思路：
判断问题的子结构（也可看作状态），当具有最优子结构时，动态规划可能适用。
求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。分治法则不同，每次递归都产生新的问题。
重新构造一个最优解。
备忘录法：
动态规划的一种变形，使用自顶向下的策略，更像递归算法。
初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。
实例可以参照矩阵链乘法部分。
1.硬币找零
难度评级：★
假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。
解法：
用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小硬币数。对于不同的硬币面值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数目的找零total，需要求解sum[total]的值。
2.字符串相似度/编辑距离（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]。
以下是相应代码。考虑到C语言数组下标从0开始，做了一个转化将字符串后移一位。
扩展1：
如何输出所有的LCS？
难度评级：★★
分析：
根据上面c[i,j]和b[i,j]的构造过程可以发现如果c[i-1,j]==c[i,j-1]，那么分别向上和向左返回的上一个状态都是可行的。如果将其标记为“左/上”并通过递归调用来生成从c[m,n]到c[1,1]的所有路径，就能找出所有的LCS。时间复杂度上界为O(mn)。
扩展2：
通过LCS获得最长递增自子序列。
分析：
对于1个序列，如243517698，最大值9，最小值1，那么通过将它与123456789求LCS得到的就是最长连续递增子序列23568。
这种做法不适用于最长连续非递减子序列，除非能获得重复最多的元素数目，如2433517698，那么可以用112233445566778899与之比较。
使用专门的最长递增子序列算法可以进行优化，详见下一部分。
4.最长递增子序列（Longest Increasing Subsequence,lis）
难度评级：★
对于一个序列如1，-1，2，-3，4，-5，6，-7，其最长第增子序列为1,2,4,6。
解法：
除了利用3中lcs来求解，这里使用求解lis问题的专门方法。
先看看如何确定子结构的表示。对于长度为k的序列s[1...k]，如果用lis[k]记录这个序列中最长子序列似乎没什么用，因为在构造lis[k+1]时，需要比较s[k]与前面长度为lis[k]的lis的最后一个元素、s[1...k]中长度为lis[k]-1的序列的最后一个元素等等，没有提供什么便利，这个方案被否决。
为了将每个lis[k]转化为构造lis[k+1]时有用的数据，把子结构记为以s[k]为结尾的lis的长度，那么对于s[k+1]，需要检查所有在它前面且小于它的元素s[i]，并令lis[k+1] = max(lis[i]+1),（i=1 to k,s[k+1]>s[i]）。这样，一个O(n2)的算法便写成了。为了在处理完成后不必再一次遍历lis[1...n]，可以使用一个MaxLength变量保存当前记录中最长的lis。
7.0-1背包
难度评级：★★
一个贼在偷窃一家商店时发现了n件物品，其中第i件值vi元，重wi磅。他希望偷走的东西总和越值钱越好，但是他的背包只能放下W磅。请求解如何放能偷走最大价值的物品，这里vi、wi、W都是整数。
解法：
如果每个物品都允许切割并只带走其一部分，则演变为部分背包问题，可以用贪心法求解。0-1背包问题经常作为贪心法不可解决的实例（可通过举反例来理解），但可以通过动态规划求解。
为了找出子结构的形式，粗略地分析发现，对前k件物品形成最优解时，需要决策第k+1件是否要装入背包。但是此时剩余容量未知，不能做出决策。因此把剩余容量也考虑进来，形成的状态由已决策的物品数目和剩余容量两者构成。这样，所有状态可以放入一个n*(W+1)的矩阵c中，其值为当前包中物品总价值，这时有
\[c[i][j]=\left\{\begin{matrix} c[i-1][j]& if \ w_{i}>j\\ \max\begin{Bmatrix} c[i-1][j-w_{i}]+v_{i} \ ,\ c[i-1][j] \end{Bmatrix} & if \ w_{i}\leqslant j \end{matrix}\right.\]
根据这个递推公式，很容易写出求解代码。
这样做的好处是，对于红线和蓝线上同一行j的点的坐标(i,j)(i',j)，总有i<=i',这样就能够把三条路线划分成左、中、右三条有序的路线。
经过两次转化，可以构造子结构了。用Max[y-1][i][j][k]表示在y-1行时，三条路线分别在i、j、k时所能取得的最大苹果数，用Max[y-1][i][j][k]可以求解任意的Max[y][i'][j'][k']，其中i' = i to j' , j' = j to k', k' = k to M. 如果线路重叠，苹果已经被取走，不用重复考虑。因此处理每一行时为了简单起见最好维护一个该位置苹果是否被取走的标志位，方便在路线重叠时计算。根据上面的范围关系，先求k'的所有情况，然后是j'，最后才是x'。这样Max[N][M][M][M]就是三趟后所能取得的最多苹果数。
参考资料
《算法导论》第15章动态规划、第16章贪心算法
《算法设计手册》第八章动态规划
《编程珠玑》相关问题
《编程之美》相关问题
poj 2411 & 编程之美 4.2 瓷砖覆盖地板
最大连续子序列乘积
Dynamic Programming: From novice to advanced
附录1：其他的一些动态规划问题与解答（链接）
双调欧几里德旅行商问题（算法导论思考题15-1）
评：网络上的很多中文版本，都不如直接看这篇文章里的英文原版解答理解的清楚。
整齐打印（算法导论思考题15-4）
评：难度不高，注意要求的是空格数的立方和最小。
动态规划应用：Viterbi算法
评：需要一些马尔科夫链的知识。理解起来不是很容易，理解以后是不是有种像是更多个生产线的装备线调度？
最高效益的调度（算法导论思考题15-7）
评：和0-1背包问题何其相似。
附录2：《算法设计手册》第八章 动态规划 面试题解答
8-24.
给定一个硬币种类的集合，找出凑出给定一个值所用的最小硬币数目。
解答：
正文问题1已做解答，略。
8-25.
长度为n的数组，其中元素可正可负可零。找出数组索引i,j使得从i到j的元素之和最大。
解答：
最大连续自序列和问题，请参考正文问题5的解答。
8-26.
假设你有一页纸，正面和背面都写满了字母，当剪掉正面上一个字母时，这一页的背面的字母也会被剪掉。设计一个算法来验证是否能通过这张纸生成一个给定的字符串？提供一个函数，当你输入一个字母的位置时能够返回它背面的字母。（叙述关键思路即可）
解答：
目前我所看到的最容易理解的解法是使用最大流来解的：http://stackoverflow.com/questions/6135443/dynamic-programming-question
下面把思路大意翻译一下。
假设需要拼成的字符串是"FOO"，同时这张纸的正反面对应位置上的内容（可以通过提供的函数获得）分别是：
位置1234正面FCOZ反面OOKZ由于位置4上的字母的正反面都用不到，忽略。
把这个表格转化成一个两层结点的流量网络
其中源点下面第一层表示拼成所需字符串的所有字母，源点到达该点的流量是需要的数目。第一层与第二层相连接表示某一位置上对应的是哪个所需字母，比如位置1正反面分别是F和O，表示它能提供1个F的入度和1个O的入度，但又由于一个片纸无论正反面只能用一次，那么它只能提供1的出度，直接连接汇点。
这个问题是否有解，等价于这个流量网络中是否存在一个流使得源点的流的出度等于汇点流的的入度，即一个最大流问题。
