1.6k 人阅读
标签：至少1个，最多5个
DP和分治的相似
都是通过组合子问题的解来求解原问题。
DP中的“programming”指的是一种表格法，而非coding。
DP和分治的不同
分治步骤：（例如归并排序）
将问题划分为互不相交的子问题
递归地求解子问题
组合子问题的解，求出原问题的解
应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）
这种情况下分治会做很多不必要的工作，会反复求解哪些公共子问题。
而DP对每个子子问题只求解一次，将其解保存在一个表格中，无需每次都重新计算，避免重复工作。
DP通常用来求解最优化问题（optimization problem）
这种问题可以有很多可行的解，每个解都有一个值，希望找到最优值（最大或最小）的解。称这样的解为问题的一个最优解（an optimal solution）,而不是最优解（the optimal solution）,因为可能有多个解都达到最优。
DP的四个步骤
刻画一个最优解的结构特征。
递归地定义最优解的值。
计算最优解的值，通常采用自底向上法。
利用计算出的信息构造一个最优解。
前三步是DP求解的基础。若仅需要一个最优解的值，而非解本身，可忽略第四步。若需第四步，有时需在执行第3步的过程中维护一些额外的信息，以便构造一个最优解。
钢条切割例子
场景：把长钢条切割为短钢条出售。切割工序本身无成本。求最佳切割方案。
假定：出售一段长度为 i 英寸的钢条的价格为Pi(i = 1, 2, …, )单位:$，钢条长度均为整英寸。下图为价格表。
问题描述：给定一段长度为n英寸的钢条和一个价格表，求切割方案，使销售收益Rn最大。注：若长度为n英寸的钢条的价格Pn足够大，最优解可能就是完全不需要切割。
考虑长度为4的情况，下图给出了4英寸钢条的所有切割方案。
切成两段各长2英寸的钢条，将产生P2 + P2 = 5 + 5 = 10 的收益，为最优解。
长度为n英寸的钢条共有2^(n-1)种不同切割方案，因为在距离钢条左端 i (i=1, 2, … , n-1)英寸处，总是可以选择切割或者不切割。用普通的加法符号表示切割方案，因此7=2+2+3表示将长度为7的钢条切割为3段：2英寸，2英寸，3英寸。
若一个最优解将钢条切割为k段（1≤k≤n），那么最优切割方案
n = i1 + i2 + … + ik.
将钢条切割为长度分别为i1, i2, … , ik的小段，得到的最大收益为
Rn = Pi1 + Pi2+…+Pik
对于上面表格的价格样例，可以观察所有最优收益值Ri (i: 1~10)以及最优方案：
长度为1：切割方案1=1（无切割）。最大收益R1 = 1
长度为2：切割方案2=2（收益5），1+1=2（收益2）。最大收益R2 = 5
长度为3：切割方案3=3（收益8），1+2=3（收益6），2+1=3（收益6）。最大收益8
长度为4：切割方案4=4（收益9），1+3=4（收益9），2+2=4（收益10），3+1=4（收益9），1+1+2=4（收益7），1+2+1=4（收益7），2+1+1=4（收益7），1+1+1+1=4（收益4）。最大收益10
长度为5：切割方案5=5（10），1+4=5（10），2+3=5（13），1+1+3=5（10），2+2+1=5（11），1+1+1+1+1=5（5），其他是前面的排列。最大收益13
依次求出。。。
更一般的，对于Rn(n≥1)，可以用更短的钢条的最优切割收益来描述它：
Rn = max(Pn, R1+Rn-1, R2 + Rn-2, … , Rn-1 + R1)
第一个参数Pn对应不切割，直接出售长度为n的方案。
其他n-1个参数对应n-1种方案。对每个i=1,2,….,n-1，将钢条切割为长度为i和n-i的两段，接着求解这两段的最优切割收益Ri和Rn-i;(每种方案的最优收益为两段的最优收益之和)。
由于无法预知哪种方案会获得最优收益，必须考察所有可能的 i ，选取其中收益最大者。若不切割时收益最大，当然选择不切割。
为了求解规模为n的原问题，先求解子问题（子问题形式完全一样，但规模更小）。
即首次完成切割后，将两段钢条看成两个独立的钢条切割问题实例。
通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中获取收益最大者，构成原问题的最优解。
称钢条切割问题满足最优子结构性质：
问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
除上述解法，问题可化简为一种相似的递归：从左边切割下长度为 i 的一段，只对右边剩下的长度为 n-i 的一段进行继续切割（递归求解），对左边一段则不再进行切割。
即问题分解的方式为：将长度为n的钢条分解为左边开始一段，以及剩余部分继续分解的结果。（这样，不做任何切割的方案可以描述为：第一段长度为n，收益为Pn，剩余部分长度为0，对应收益为R0 = 0）。于是得到上面公式的简化版本：
在此公式中，原问题的最优解只包含一个相关子问题（右端剩余部分的解），而不是两个。
自顶向下递归实现的伪代码：Cut-Rod(p, n)
Cut-Rod(p, n)
for i = 1 to n
q = max(q, p[i] + Cut-Rod(p, n-i))
该过程以价格数组p[1...n]和整数n为输入，返回长度为n的钢条的最大收益。
若n=0，不可能有任何收益，所以第二行返回0.
第3行将最大收益初始化为负无穷，以便第4第5行的for循环能正确计算。
第6行返回结果。Java实现如下：
* 钢条切割
public class CutRob {
public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
public static int solution(int length){
if(length == 0)
int result = Integer.MIN_VALUE;
for(int i = 1; i &= i++){
result = Math.max(result, prices[i-1] + solution(length-i));
public static void main(String[] args) {
for(int i=1; i&= prices. i++)
System.out.println("长度为"+i+"的最大收益为："+solution(i));
长度为1的最大收益为：1
长度为2的最大收益为：5
长度为3的最大收益为：8
长度为4的最大收益为：10
长度为5的最大收益为：13
长度为6的最大收益为：17
长度为7的最大收益为：18
长度为8的最大收益为：22
长度为9的最大收益为：25
长度为10的最大收益为：30
该递归很好理解，但是一旦规模较大，程序运行时间会暴涨，课本上说对n=40要好几分钟，很可能超过1小时，本次实验一下n=33. (假设从钢条长度超过10开始价格就一直保持在30美元)
public class CutRob {
public static int[] prices =
{1,5,8,9,10,17,17,20,24,30,
30,30,30,30,30,30,30,30,30,30,
30,30,30,30,30,30,30,30,30,30,
30,30,30};
public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
public static int solution(int length){
if(length == 0)
int result = Integer.MIN_VALUE;
for(int i = 1; i &= i++){
result = Math.max(result, prices[i-1] + solution(length-i));
public static void main(String[] args) {
long curr = System.currentTimeMillis();
System.out.println("长度为33的最大收益为："+solution(33));
System.out.println(System.currentTimeMillis() - curr);
长度为33的最大收益为：98
该递归计算结果用了几乎26秒。当输入长度继续增大，会消耗更长的时间。
为什么效率这么差？原因在于，CutRob反复的用相同的参数值对自身进行递归调用，即反复的求解子问题。
下图显示了n=4时的调用过程CutRob(p, n)对i=1,2,…,n调用CutRob( p,n-i )，等价于对j=0,1,…,n-1调用CutRob( p, j )，该递归展开时，所做的工作量会爆炸性增长。
为了分析该算法运行时间，令T(n)表示第二个参数值为n时函数的调用次数。此值等于递归调用树中 根为n的子树中的节点总数，注意，此值包含了根节点对应的最初的一次调用。因此T(0)=1,且
第一项 ’1’ 表示函数的第一次调用（递归调用树的根节点），T( j )为调用cutrob(p, n-i)所产生的所有调用次数。T(n) = 2^n。即该算法的运行时间为n的指数函数。
回头看下，该运行时间并不令人惊讶。对于长度为n的钢条，该算法显然考察了所有2^(n-1)种可能的切割方案。递归调用树中共有2^(n-1)个叶子节点，每个叶子节点对应一种可能的切割方案。对每条从根到叶子的路径，路径上的标号给出了每次切割前右边剩余部分的长度（子问题规模）。也就是说，标号给出了对应的切割点（从钢条右端测量）。
看完了递归解法以及其暴涨的复杂度。下面来看下用DP怎么来解决钢条切个问题。思想如下：
已经看到，朴素递归算法之所以效率低，是因为反复求解相同的子问题。
DP会仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要次子问题的解，只需查找保存的结果，而不必重新计算。
因此DP用空间来节省时间。是典型的时空权衡例子（time-memory trade-off）。
如果子问题数量是输入规模的多项式函数，则可以在多项式时间内求解出每个子问题。其总时间复杂度就是多项式阶的。
DP有两种等价的实现方法：带备忘的自顶向下法（top-down with memoization）& 自底向上法（bottom-up method）。
带备忘的自顶向下法（top-down with memoization）
此方法仍然按照自然的递归形式编写过程，但是过程会保存每个子问题的解（通常保存在一个数组或散列表中）。
当需要一个子问题的解时，过程首先检查是否已经保存过此解，
如果是，则直接返回保存的值，从而节省了计算时间；
否则，按照通常方式计算这个子问题。
自底向上法（bottom-up method）
该方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。
因而可以将子问题按规模排序，按由小到大的顺序进行求解。
当求解某个子问题时，所依赖的那些更小的子问题都已经求解完毕，结果已经保存。
每个子问题只求解一次，当求解它时（也是第一次遇到它），所有前提子问题都已经求解完成。
两种方法得到的算法具有相同的渐进运行时间，
仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。
由于没有频繁的递归调用开销，自底向上的复杂度函数通常具有更小的系数。
算法伪代码-带备忘的自顶向下法（top-down with memoization）
mem-cut-rod(p, n)
let r[0…n] be a new array
for i=0 to n
r[i] = -∞
return mem-cut-rod-aux(p, n, r)
mem-cut-rod-aux(p, n, r)
if r[n] &= 0
return r[n]
for i=1 to n
q = max(q, p[i] + mem-cut-rod-aux(p, n-i, r))
主过程 mem-cut-rod(p, n)将辅助数组r[0...n]初始化为负无穷，然后调用辅助过程mem-cut-rod-aux(最初cut-rob引入备忘机制的版本)。伪代码解读：
首先检查所需值是否已知（第1行）;
如果是，则第2行直接返回保存的值;
否则第3~8行用通常方法计算所需值q;
第9行将q存入r[n]中;
第10行返回;
自底向上版本更简单：
bottom-up-cut-rod(p, n)
let r[0…n] be a new array
for j=1 to n
for i=1 to j
q = max(q, p[i] + r[j-i])
return r[n]
自底向上版本采用子问题的自然顺序：若i&j，则规模为i的子问题比规模为j的子问题“更小”。因此，过程依次求解规模为j=0,1,…,n的子问题。伪代码详解：
第1行创建一个新数组r[0...n]来保存子问题的解；
第2行将r[0]初始化为0，因为长度为0的钢条没有收益；
第3~6行对j=1...n按升序求解每个规模为j的子问题。求解方法与cut-rod采用的方法相同，只是现在直接访问数组元素r[j-i]来获取规模为j-i的子问题的解，而不必进行递归调用；
第7行将规模为 j 的子问题的解存入r[j]；
第8行返回r[n],即最优解
两种方法具有相同的渐进运行时间。
bottom-up-cut-rod 主体是嵌套的双层循环，内层循环（5~6行）的迭代次数构成一个等差数列和，不难分析时间为n^2.
mem-cut-rod 运行时间也是n^2，其分析略难：当求解一个之前已经计算出结果的子问题时，递归调用会立即返回，即每个子问题只求解一次，而它求解了规模为0，1，。。。，n的子问题；为求解规模为n的子问题，第6~7行的循环会迭代n次；因此进行的所有递归调用执行此for循环的迭代次数也是一个等差数列，其和也是n^2。
Java实现：
public class CutRob {
public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
/** 自顶向下*/
public static int mem_cut_rod(int n){
int[] dp = new int[n+1];
// 辅助数组dp
Arrays.fill(dp, Integer.MIN_VALUE);
// 初始化为负无穷
return mem_cut_rod_aux(n, dp);
/** 自顶向下法的辅助函数*/
private static int mem_cut_rod_aux(int n, int[] dp) {
if(dp[n] &= 0)
return dp[n]; // 如果子问题已经解过，直接返回
int max = Integer.MIN_VALUE;
// 如果长度为0，则最大收益为0
// 长度若不为0
for(int i = 1; i&=n; i++)
// 找到最大收益
max = Math.max(max, prices[i-1] + mem_cut_rod_aux(n-i, dp));
// 把计算得到的最大收益存入结果
// 返回结果
public static void main(String[] args) {
for(int i=1; i&=prices. i++)
System.out.println("长度为"+i+"的最大收益为："+mem_cut_rod(i));
长度为1的最大收益为：1
长度为2的最大收益为：5
长度为3的最大收益为：8
长度为4的最大收益为：10
长度为5的最大收益为：13
长度为6的最大收益为：17
长度为7的最大收益为：18
长度为8的最大收益为：22
长度为9的最大收益为：25
长度为10的最大收益为：30
自底向上：
public class CutRob {
public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
/** 自底向上法*/
private static int bottom_up_cut_rod(int n){
int[] dp = new int[n+1];
dp[0] = 0;
for(int j=1; j&=n; j++){
int max = Integer.MIN_VALUE;
for(int i=1; i&=j; i++){
max = Math.max(max, prices[i-1] + dp[j-i]);
return dp[n];
public static void main(String[] args) {
for(int i=1; i&=prices. i++)
System.out.println("长度为"+i+"的最大收益为："+bottom_up_cut_rod(i));
下面来从运行结果的时间上做一个对比，这里拿自底向上法来和前面的递归做对比。
上面的朴素递归只把输入的n增加到33，就运行了25507毫秒。下面来看下自底向上。
public class CutRob {
public static int[] prices =
{1,5,8,9,10,17,17,20,24,30,
30,30,30,30,30,30,30,30,30,30,
30,30,30,30,30,30,30,30,30,30,
30,30,30,30,30,30,30,30,30,30,
30,30,30,30,30,30,30,30,30,30,
30,30,30};
public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
/** 自底向上法*/
private static int bottom_up_cut_rod(int n){
int[] dp = new int[n+1];
dp[0] = 0;
for(int j=1; j&=n; j++){
int max = Integer.MIN_VALUE;
for(int i=1; i&=j; i++){
max = Math.max(max, prices[i-1] + dp[j-i]);
return dp[n];
public static void main(String[] args) {
long curr = System.currentTimeMillis();
System.out.println(“长度为53的最大收益为："+bottom_up_cut_rod(53));
System.out.println(System.currentTimeMillis() - curr);
用自底向上把输入增加到53，整个过程也就运行了1毫秒。
长度为53的最大收益为：158
子问题图：
当思考一个DP问题时，应弄清楚所涉及的子问题以及子问题之间的依赖关系。
问题的子问题图准确的表达了这些信息。下图展示了n=4时钢条切割问题的子问题图。
它是一个有向图，每个顶点唯一对应一个子问题。
若求子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就会有一条从子问题x的顶点到子问题y的顶点的有向边。
例如，若自顶向下过程在求解x时需要直接递归调用自身来求解y，那么子问题图就包含从x到y的一条有向边。
可以将子问题图看做自顶向下递归调用树的“简化版”或“收缩版”，因为树中所有对应相同子问题的节点合并为图中的单一顶点，相关的所有边都从父节点指向子节点。
自底向上的DP方法处理子问题图中顶点的顺序为：对于一个给定的子问题x，在求解它之前求解邻接至它的子问题y。
用22章的术语说，自底向上动态规划算法是按“逆拓扑排序”或者“反序的拓扑排序”来处理子问题图中的顶点。
换句话说，对于任何子问题，直至它所依赖的所有子问题均已求解完成，才会求解它。
类似的，可以用22章中的术语“深搜”来描述（带备忘机制的）自顶向下动态规划算法处理子问题图的顺序。（22.3节）
子问题图G = ( V, E )的规模可以帮助我们确定DP算法的运行时间。
由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。
通常，一个子问题的求解时间与子问题图中对应顶点的度（出射边的数目）成正比，而子问题的数目等于子问题图的顶点数。
因此，DP算法运行时间与顶点和边的数量成线性关系。
前文给出的钢条切割DP算法返回最优解的收益值，并未返回解本身（一个长度列表，给出切割后每段钢条的长度）。
我们可以扩展DP算法，使之对于每个问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，就能输出最优解。
下面给出bottom-up-cut-rob的扩展版本，它对于长度为j 的钢条不仅计算最大收益值Rj, 还保存最优解对应的第一段钢条的切割长度Sj：
extended-bottom-up-cut-rod(p, n)
let r[0…n] and s[0…n] be new arrays
for j=1 to n
for i=1 to j
if q & p[i]+r[j-i]
q = p[i]+r[j-i]
return r and s
此过程和bottom-up-cut-rob很相似，差别只是在第1行创建了数组s，并在求解规模为j的子问题时，将第一段钢条的最优切割长度i保存在s[ j ]中（第8行）。
下面的过程接受两个参数：价格表p和钢条长度n，然后调用extended-bottom-up-cut-rod来计算切割下来的每段钢条的长度s[1...n]，最后输出长度为n的钢条的完整的最优切割方案：
print-cut-rob-solution(p, n)
(r, s) = extended-bottom-up-cut-rod(p, n)
print s[n]
n = n-s[n]
对于前文给出的钢条切割实例，extended-bottom-up-cut-rod(p, 10)会返回下面的数组：
这个表一定要根据代码逻辑亲手画一遍。体会其构建过程。
对此例调用print-cut-rod-solution(p,10)只会输出10，但对n=7，会输出最优方案R7切割出的两段钢条长度1和6。看看Java代码实现：
public class CutRob {
public static int[] prices = {1,5,8,9,10,17,17,20,24,30};
private static int[]
/** 带切割方案的自底向上扩展方案*/
public static int extended_bottom_up_cut_rod(int n){
int[] dp = new int[n+1];
path = new int[n+1];
dp[0] = 0;
for(int j = 1; j&=n; j++){
int max = Integer.MIN_VALUE;
for(int i=1; i&=j; i++){
if(max & (prices[i-1] + dp[j-i])){
max = prices[i-1] + dp[j-i];
return dp[n];
/** 得到切割方案(一个最优解)*/
public static ArrayList&Integer& getACutSolution(int n){
ArrayList&Integer& result = new ArrayList&&();
while(n & 0){
result.add(path[n]);
n -= path[n];
public static void main(String[] args) {
System.out.println("长度为7的最大收益为："+extended_bottom_up_cut_rod(7));
System.out.println(getACutSolution(7));
长度为7的最大收益为：18
至此，对DP有了一个刚刚开始的了解。
0 收藏&&|&&0
你可能感兴趣的文章
你可能感兴趣的文章
分享到微博？
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。动态规划的工作量分配问题，能不能用这个方法求解？ - 知乎有问题，上知乎。知乎作为中文互联网最大的知识分享平台，以「知识连接一切」为愿景，致力于构建一个人人都可以便捷接入的知识分享网络，让人们便捷地与世界分享知识、经验和见解，发现更大的世界。2被浏览57分享邀请回答0添加评论分享收藏感谢收起写回答常见的动态规划问题分析与求解
动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一，并不像回溯法具有解决绝大多数问题的银弹（)。为了解决动态规划问题，只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集，希望能有所帮助。难度评级受个人主观影响较大，仅供参考。
目录（点击跳转）
动态规划求解的一般思路：&
判断问题的子结构（也可看作状态），当具有最优子结构时，动态规划可能适用。
求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。分治法则不同，每次递归都产生新的问题。
重新构造一个最优解。
备忘录法：
动态规划的一种变形，使用自顶向下的策略，更像递归算法。
初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。
实例可以参照矩阵链乘法部分。&
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]的值。
typedef struct {
int nC //使用硬币数量
//以下两个成员是为了便于构造出求解过程的展示
int lastS//上一个状态
int addC//从上一个状态达到当前状态所用的硬币种类
state *sum = malloc(sizeof(state)*(total+<span style="color:#));
for(i=<span style="color:#;i&=i++)
sum[i].nCoin = INF;
sum[<span style="color:#].nCoin = <span style="color:#;
sum[<span style="color:#].lastSum = <span style="color:#;
for(i=<span style="color:#;i&=i++)
for(j=<span style="color:#;j&n;j++)
if(i-coin[j]&=<span style="color:# && sum[i-coin[j]].nCoin+<span style="color:#&sum[i].nCoin)
sum[i].nCoin = sum[i-coin[j]].nCoin+<span style="color:#;
sum[i].lastSum =
sum[i].addCoin = coin[j];
if(sum[total].nCoin == INF)
printf(&can't make change.\n&);
return <span style="color:#;
通过sum[total].lastSum和sum[total].addCoin，很容易通过循环逆序地或者编写递归调用的函数正序地输出从结束状态到开始状态使用的硬币种类。以下各题输出状态转换的方法同样，不再赘述。下面为了方便起见，有的题没有在构造子结构的解时记录状态转换，如果需要请类似地完成。
(1)一个矩形区域被划分为N*M个小矩形格子，在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，最后到达(N,M)，每经过一个格子就把其中的苹果全部拿走。请找出能拿到最多苹果数的路线。
难度评级：★
这道题中，当前位置(i,j)是状态，用M[i][j]来表示到达状态(i,j)所能得到的最多苹果数，那么M[i][j] = max(M[i-1][j],M[i][j-1]) + A[i][j] 。特殊情况是M[1][1]=A[1][1]，当i=1且j!=1时,M[i][j] = M[i][j-1] + A[i][j]；当i!=1且j=1时M[i][j] = M[i-1][j] + A[i][j]。
求解程序略。
(2)装配线调度（《算法导论》15.1）
难度评级：★
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开始，做了一个转化将字符串后移一位。
#include &stdio.h&
#include &string.h&
#define MAXLEN 20
#define MATCH 0
#define INSERT 1
#define DELETE 2
typedef struct {
cell m[MAXLEN+<span style="color:#][MAXLEN+<span style="color:#];
int match(char a,char b)
//cost of match
//not match:1
return (a==b)?<span style="color:#:<span style="color:#;
int string_compare(char *s,char *t)
int i,j,k;
int opt[<span style="color:#];
//row_init(i);
for(i=<span style="color:#;i&=MAXLEN;i++) {
m[i][<span style="color:#].cost =
if(i==<span style="color:#)
m[i][<span style="color:#].parent = -<span style="color:#;
m[i][<span style="color:#].parent = INSERT;
//column_init(i);
for(i=<span style="color:#;i&=MAXLEN;i++) {
m[<span style="color:#][i].cost =
if(i==<span style="color:#)
m[<span style="color:#][i].parent = INSERT;
char m_s[MAXLEN+<span style="color:#] = & &,m_t[MAXLEN+<span style="color:#] =& &;
strcat(m_s,s);
strcat(m_t,t);
for(i=<span style="color:#;i&=strlen(s);i++)
for(j=<span style="color:#;j&=strlen(t);j++) {
opt[MATCH] = m[i-<span style="color:#][j-<span style="color:#].cost + match(m_s[i],m_t[j]);
opt[INSERT] = m[i][j-<span style="color:#].cost + <span style="color:#;
opt[DELETE] = m[i-<span style="color:#][j].cost + <span style="color:#;
m[i][j].cost = opt[MATCH];
m[i][j].parent = MATCH;
for(k=INSERT;k&=DELETE;k++)
if(opt[k]&m[i][j].cost)
m[i][j].cost = opt[k];
m[i][j].parent =
//goal_cell(s,t,&i,&j);
return m[i][j].
int main() {
char t[] = &you should not&;
char p[] = &thou shalt not&;
int n = string_compare(t,p);
printf(&%d\n&,n);
字符串相似度/edit distance
(1)子串匹配
难度评级：★★
修改两处即可进行子串匹配：
row_init(int i)
m[<span style="color:#][i].cost = <span style="color:#; /* note change */
m[<span style="color:#][i].parent = -<span style="color:#; /* note change */
goal_cell(char *s, char *t, int *i, int *j)
int /* counter */
*i = strlen(s) - <span style="color:#;
*j = <span style="color:#;
for (k=<span style="color:#; k&strlen(t); k++)
if (m[*i][k].cost & m[*i][*j].cost) *j =
如果j= strlen(S) - strlen(T)，那么说明T是S的一个子串。
（这部分是根据《算法设计手册》8.2.4和具体实例Skiena与Skienaa、Skiena与somta的分析获得的，解释不够全面，可能有误，请注意）
(2)最长公共子序列
难度评级：★★
将match时不匹配的代价转化为最大长度即可：
int match(char c, char d)
if (c == d) return(<span style="color:#);
else return(MAXLEN);
此时，最小值是两者不同部分的距离。
（这部分同样也不好理解，对于最长公共子序列，建议直接使用下一部分中的解法）
如果在编辑距离中各个操作的代价不同，如何寻找最小代价？&
3.最长公共子序列(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}。求出一个即可。
和2类似，对于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；
下面是《算法导论》上用伪码描述的lcs算法。其中c[i][j]记录当前lcs长度，b[i][j]记录到达该状态的上一个状态。
如何输出所有的LCS？
难度评级：★★
根据上面c[i,j]和b[i,j]的构造过程可以发现如果c[i-1,j]==c[i,j-1]，那么分别向上和向左返回的上一个状态都是可行的。如果将其标记为“左/上”并通过递归调用来生成从c[m,n]到c[1,1]的所有路径，就能找出所有的LCS。时间复杂度上界为O(mn)。
通过LCS获得最长递增自子序列。
对于1个序列，如，最大值9，最小值1，那么通过将它与求LCS得到的就是最长连续递增子序列23568。
这种做法不适用于最长连续非递减子序列，除非能获得重复最多的元素数目，如，那么可以用778899与之比较。
使用专门的最长递增子序列算法可以进行优化，详见下一部分。
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。
typedef struct {
//算法核心
state *a = malloc(sizeof(state) * n);
for(i=<span style="color:#;i&n;i++) {
a[i].length = <span style="color:#;
a[i].prev = -<span style="color:#;
for(i=<span style="color:#;i&n;i++)
for(j=<span style="color:#;j&i;j++)
if(array[i]&array[j] && a[i].length & a[j].length + <span style="color:#)
a[i].length = a[j].length + <span style="color:#;
a[i].prev =
if(a[i].length & max_length) {
max_length = a[i].
求解lis的加速
&难度评级：★★
在构造lis[k+1]的时候可以发现，对于s[k+1]，真正有用的元素s[i]&s[k+1]且lis[i]最大。如果记录了不同长度的lis的末尾元素，那么对于新加入的元素s[k+1]，找出前面比它小的且对应lis最长的，就是以s[k+1]为结尾的lis[k+1]的长度。
可以发现使用数组MaxV[1...MAXLENGTH]其中MaxV[i]表示长度为i的lis的最小末尾元素，完全可以在s[k+1]时进行lis[k+1]的更新。进一步地发现，其实lis[]数组已经没有用了，对于MaxV[1...MAXLENGTH]中值合法对应的最大下标，就是当前最长的lis，也即利用MaxV[]更新自身。
同时，根据MaxV[]的更新过程，可以得出当i&j时，MaxV[i]&MaxV[j]（假设出现了i&j且Max[i]=&Max[j]的情况，那么在之前的处理中，在发现j长度的lis时，应用它的第i个元素来更新Max[i]，仍会导致MaxV[i]&MaxV[j]，这与这个现状发生了矛盾，也即这个情况是不可能到达的）。这样，在寻找小于s[k+1]的值时，可以使用二分查找，从而把时间复杂度降低至O(nlogn)。
int lis_ologn(int *array, int length) {
int i, left,right,mid,max_len = <span style="color:#;
int *MaxV;
if(!array)
return <span style="color:#;
MaxV = (int*)malloc(sizeof(int)*(length+<span style="color:#));
MaxV[<span style="color:#] = -<span style="color:#;
MaxV[<span style="color:#] = array[<span style="color:#];
for(i=<span style="color:#;i&i++){
//寻找范围是MaxV[1, ... , max_len]
left = <span style="color:#;
right = max_
//二分查找MaxV中第一个大于array[i]的元素
while(left&right) {
mid = (left+right)/<span style="color:#;
if(MaxV[mid]&=array[i])
left = mid + <span style="color:#;
else if(MaxV[mid]&array[i])
if((MaxV[right]&array[i])&&(MaxV[right-<span style="color:#]&array[i]))
MaxV[right] = array[i];
else if (MaxV[right]&array[i]) {
MaxV[right+<span style="color:#] = array[i];
max_len++;
return max_
& 在这个解法下，不妨考虑如何重构这个lis。
5.最大连续子序列和/积
难度评级：★
输入是具有n个数的向量x，输出时输入向量的任何连续子向量的最大和。
求和比较简单，以前写过比较全面的分析：
这里只把O(n)的动态规划解法列在下面，其中只用一个变量保存过去的状态：
int max_array_v4(int *array,int length) {
int maxsofar = NI;
int maxendinghere = <span style="color:#;
for(i=<span style="color:#;i&i++) {
maxendinghere = maxnum(maxendinghere + array[i],array[i]);
//分析：maxendinghere必须包含array[i]
//当maxendinghere&0且array[i]&0，maxendinghere更新为两者和
//当maxendinghere&0且array[i]&0，maxendinghere更新为两者和
//当maxendinghere&0且array[i]&0，maxendinghere更新为array[i]
//当maxendinghere&0且array[i]&0，maxendinghere更新为array[i]
maxsofar = maxnum(maxsofar,maxendinghere);
难度评级：★
给定一个正浮点数数组，求它的一个最大连续子序列乘积的值。
对数组中每个元素取对数，构成新的数列，在新的数列上使用求最大连续子序列的算法。
如果求对数开销较大，建议使用扩展2的方法。
难度评级：★
给定一个浮点数数组，其值可正可负可零，求它的一个最大连续子序列乘积的值。（假定计算过程中，任意一个序列的积都不超过浮点数最大表示）
在最大连续子序列和算法的基础上进行修改。由于负负得正，对于当前状态array[k]，需要同时计算出它的最大值和最小值。即：
new_maxendinghere = max3(maxendinghere*array[k],minendinghere*array[k],array[k])
new_minendinghere = min3(maxendinghere*array[k],minendinghere*array[k],array[k])
此后对已遍历部分的最大积进行更新：
maxsofar = max(maxsofar,new_maxendinghere)
如果不习惯用常数个变量来表示，可以看看，再想想用数组保存是不是浪费了空间。（计算max[k]、min[k]只用到了max[k-1]、min[k-1]，没有必要保存全部状态）
6.矩阵链乘法
难度评级：★
一个给定的矩阵序列A1A2...An计算连乘乘积，有不同的结合方法，并且在结合时，矩阵的相对位置不能改变，只能相邻结合。根据矩阵乘法的公式，10*100和100*5的矩阵相乘需要做10*100*5次标量乘法。那么对于维数分别为10*100、100*5、5*50的矩阵A、B、C，用(A*B)*C来计算需要10*100*5 + 10*5*500 =7500次标量乘法；而A*(B*C)则需要100*5*50+10*100*50=75000次标量乘法。
那么对于由n个矩阵构成的链&A1,A2,...,An&，对i-1,2,...n，矩阵Ai的维数为pi-1*pi，对乘积A1A2...An求出最小化标量乘法的加括号方案。
尽管可以通过递归计算取1&=k&n使得P(n)=∑P(k)P(n-k)，遍历所有P(n)种方案，但这并不是一个高效率的解法。
经过以上几道题的锻炼，很容易看出，子结构是求Ai...Aj的加括号方法m[i][j]可递归地定义为
\[m[i][j]=\left\{\begin{matrix} 0& if \ i=j\\ \underset{i\leqslant k&j}{min}\begin{Bmatrix} m[i][k] + & m[k+1][j] +& p_{i-1}p_{k}p_{j} \end{Bmatrix} & if \ i&j \end{matrix}\right.\]
这样，只需利用子结构求解m[1][n]即可，并在在构造m[1][n]的同时，记录状态转换。下面的代码展示了这个过程，不再仔细分析。
#include &stdio.h&
#include &stdlib.h&
#define ULT
int print_optimal_parens(int **s,int i, int j)
printf(&A%d&,i+<span style="color:#);
printf(&(&);
print_optimal_parens(s,i,*(*(s+i)+j));
print_optimal_parens(s,*(*(s+i)+j)+<span style="color:#,j);
printf(&)&);
return <span style="color:#;
int matrix_chain_order(int *p, int n) {
int i,j,k,l,q;
int **m, **s;
m=(int **)malloc(n*sizeof(int*));
for(i=<span style="color:#;i&n;i++)
m[i]=(int*)malloc(n*sizeof(int));
s=(int **)malloc(n*sizeof(int*));
for(i=<span style="color:#;i&n;i++)
s[i]=(int*)malloc(n*sizeof(int));
for(i=<span style="color:#;i&n;i++)
s[i][i] = <span style="color:#;
//m,s可以被压缩存储在上三角矩阵
for(l=<span style="color:#;l&=n;l++) {
for (i=<span style="color:#;i&n-l+<span style="color:#;i++) {
j = i+l-<span style="color:#;
m[i][j] = ULT;
for (k=i; k&j;k++)
q = m[i][k] + m[k+<span style="color:#][j] + p[i-<span style="color:#+<span style="color:#]*p[k+<span style="color:#]*p[j+<span style="color:#];
if (q&m[i][j])
/*display m[i][j]*/
for (i=0;i&n;i++) {
for (j=0;j&n;j++)
printf(&%d &,m[i][j]);
printf(&\n&);
print_optimal_parens(s,<span style="color:#,<span style="color:#);
printf(&\n&);
return <span style="color:#;
int main() {
int p[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
n = (sizeof(p)/sizeof(int))-<span style="color:#;
matrix_chain_order(p,n);
return <span style="color:#;
矩阵链乘法
矩阵链乘法的备忘录解法（伪码），来自《算法导论》第15章。
难度评级：★★
一个贼在偷窃一家商店时发现了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.\]
根据这个递推公式，很容易写出求解代码。
#include &stdio.h&
#include &stdlib.h&
int package_dp(int *v,int *w,int n,int total) {
int i,j,tmp1,tmp2;
int **c = (int **)malloc((n+<span style="color:#)*sizeof(int *));
for(i=<span style="color:#;i&n+<span style="color:#;i++)
c[i]=(int *)malloc((total+<span style="color:#)*sizeof(int));
for(i=<span style="color:#,j=<span style="color:#;j&j++)
c[i][j] = <span style="color:#;
for(i=<span style="color:#;i&=n;i++) {
c[i][<span style="color:#] = <span style="color:#;
for(j=<span style="color:#;j&=j++) {
if(w[i]&j)
c[i][j] = c[i-<span style="color:#][j];
tmp1 = v[i]+c[i-<span style="color:#][j-w[i]];
tmp2 = c[i-<span style="color:#][j];
c[i][j]=(tmp1&tmp2?tmp1:tmp2);
printf(&c[%d][%d]:%d\n&,n,total,c[n][total]);
return <span style="color:#;
int main() {
int v[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
int w[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
int total = <span style="color:#0;
package_dp(v,w,sizeof(v)/sizeof(int)-<span style="color:#,total);
return <span style="color:#;
0-1背包问题示例代码
8.有代价的最短路径
难度评级：★★★
无向图G中有N个顶点，并通过一些边相连接，边的权值均为正数。初始时你身上有M元，当走过i点时，需要支付S(i)元，如果支付不起表示不能通过。请找出顶点1到顶点N的最短路径。如果不存在则返回一个特殊值，如果存在多条则返回最廉价的一条。限制条件：1&N&=100; 0&=M&=100 ; 对任意i, 0&=S[i]&=100。
如果不考虑经过顶点时的花费，这就简化成了一个一般的两点间最短路径问题，可以用Dijkstra算法求解。加入了花费限制之后，就不能直接求解了。
考察从顶点0到达顶点i的不同状态，会发现它们之间的区别是：总花费相同但路径长度不同、总花费不同但路径长度不同。为了寻找最短路径，必然要保存到达i点的最短路径；同时为了找到最小开销，应该把到达i点的开销也进行保存。根据题目的数值限制，可以将总开销作为到达顶点i的一个状态区分。这样，就可以把Min[i][j]表示为到达顶点i（并经过付钱）时还剩余j元钱的最短路径的长度。在此基础上修改Dijkstra算法，使其能够保存到达同一点不同花费时的最短长度，最终的Min[N-1][0...M]中最小的即为所求。以下是求解过程的伪代码。
对所有的(i,j),Min[i][j] = ∞,state[i][j] =
Min[<span style="color:#][M] = <span style="color:#;
while(<span style="color:#) {
for 所有unvisited的(i,j)找出M[i][j]最小的，记为(k,l)
if Min[k][l] = ∞
state[k][l] =
for 所有顶点k的邻接点p
if (l-S[p]&=<span style="color:# && Min[p][<span style="color:#-S[p]]&Min[k][l]+Dist[k][p])
Min[p][<span style="color:#-S[p]] = Min[k][l]+Dist[k][p];
//通过Dijstra算法寻找不同花费下的最小路径
for 所有j，找出Min[N-<span style="color:#][j]最小的
如果存在多个j，那么选出其中j最大的
9.瓷砖覆盖（状态压缩DP）
难度评级：★★★
用 1 * 2 的瓷砖覆盖 n * m 的地板，问共有多少种覆盖方式？
（启发来自于：，下文叙述做了点修改）
分析子结构，按行铺瓷砖。一块1*2瓷砖，横着放对下一行的状态没有影响；竖着放时，下一行的对应一格就会被占用。因此，考虑第i行的铺法时只需考虑由第i-1行造成的条件限制。枚举枚举第i-1行状态即可获得i行可能的状态，这里为了与链接一文一致，第i-1行的某格只有两个状态：空或者放置。空表示第i行对应位置需要放置一个竖着的瓷砖，这时在铺第i行时，除去限制以外，只需考虑放还是不放横着的瓷砖这2种情况即可（不必分为放还是不放、横到下一层还是竖着一共4种）。同时对于第i-1行的放法，用二进制中0和1表示有无瓷砖，那么按位取反恰好就是第i行的限制条件。
//原作者：limchiang
//出处：http://blog.csdn.net/limchiang/article/details/8619611
#include &stdio.h&
#include &string.h&
/** n * m 的地板 */
/** dp[i][j] = x 表示使第i 行状态为j 的方法总数为x */
__int64 dp[<span style="color:#][<span style="color:#49];
/* 该方法用于搜索某一行的横向放置瓷砖的状态数,并把这些状态累加上row-1 行的出发状态的方法数
* @name row 行数
* @name state 由上一行决定的这一行必须放置竖向瓷砖的地方，s的二进制表示中的1 就是这些地方
* @name pos 列数
* @name pre_num row-1 行的出发状态为~s 的方法数
void dfs( int row, int state, int pos, __int64 pre_num )
/** 到最后一列
if( pos == m ){
dp[row][state] += pre_
/** 该列不放 */
dfs( row, state, pos + <span style="color:#, pre_num );
/** 该列和下一列放置一块横向的瓷砖 */
if( ( pos &= m-<span style="color:# ) && !( state & ( <span style="color:# && pos ) ) && !( state & ( <span style="color:# && ( pos + <span style="color:# ) ) ) )
dfs( row, state | ( <span style="color:# && pos ) | ( <span style="color:# && ( pos + <span style="color:# ) ), pos + <span style="color:#, pre_num );
int main()
while( scanf(&%d%d&,&n,&m) && ( n || m ) ){
/** 对较小的数进行状压，已提高效率 */
if( n & m ){
memset( dp, <span style="color:#, sizeof( dp ) );
/** 初始化第一行 */
dfs( <span style="color:#, <span style="color:#, <span style="color:#, <span style="color:# );
for( int i = <span style="color:#; i &= i ++ )
for( int j = <span style="color:#; j & ( <span style="color:# && m ); j ++ ){
if( dp[i-<span style="color:#][j] ){
__int64 tmp = dp[i-<span style="color:#][j];
/* 如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块，
* 所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态
dfs( i, ( ~j ) & ( ( <span style="color:# && m ) - <span style="color:# ), <span style="color:#, tmp ) ;
else continue;
/** 注意并不是循环i 输出 dp[n][i]中的最大值 */
printf( &%I64d\n&,dp[n][(<span style="color:#&&m)-<span style="color:#] );
return <span style="color:#;
10.工作量划分
难度评级：★★
假设书架上一共有9本书，每本书各有一定的页数，分配3个人来进行阅读。为了便于管理，分配时，各书要求保持连续，比如第1、2、3本书分配给第1人，4、5分配给第二人，6，7，8，9分配给第3人，但不能1，4，2分配给第1人，3，5，6分配给第2人。即用两个隔板插入8个空隙中将9本书分成3部分，书不能换位。同时，分配时必须整本分配，同一本书不能拆成两部分分给两个人。为了公平起见，需要将工作量最大的那一部分最小化，请设计分配方案。用s1,...,sn表示各本书的页数。
继续从子结构的角度出发，发现如果前面的k-1份已经分好了，那么第k份自然也就分好了。用M[n][k]表示将n本书分成k份时最小化的k份中的最大工作量，从第k份也就是最后一份的角度来看，总数-它的不同情况下数量 = 前k-1份的数量和。
\[M[n][k] = \overset{n}{\underset{i=1}{min}}\max(M[i][k-1],\sum_{j=i+1}^{n}s_{j})\]
& 除此以外，初始化为
\[M[1][k] = s_{1},for \ all \ k&0\\ M[n][1] = \sum_{i=1}^{n}s_{1}\]
自底向上地可以求得使M[n][k]最小化的解。
#include &stdio.h&
#define MAXN 9
#define MAXINT 32767
void print_books(int s[],int start,int end);
int reconstruct_partition(int s[],int d[MAXN+<span style="color:#][MAXN+<span style="color:#],int n,int k);
int max(int a,int b);
int max(int a,int b)
int partition(int s[],int n,int k)
int m[MAXN+<span style="color:#][MAXN+<span style="color:#];
int d[MAXN+<span style="color:#][MAXN+<span style="color:#];
int p[MAXN+<span style="color:#];
int i,j,x;
p[<span style="color:#] = <span style="color:#;
for(i=<span style="color:#;i&=n;i++)
p[i] = p[i-<span style="color:#]+s[i-<span style="color:#];
for(i=<span style="color:#;i&=n;i++)
m[i][<span style="color:#] = p[i];
for(j=<span style="color:#;j&=k;j++)
m[<span style="color:#][j] = s[<span style="color:#];
for(i=<span style="color:#;i&=n;i++)
for(j=<span style="color:#;j&=k;j++)
m[i][j] = MAXINT;
for(x=<span style="color:#;x&=(i-<span style="color:#);x++)
cost = max(m[x][j-<span style="color:#],p[i]-p[x]);
if(m[i][j]&cost) {
reconstruct_partition(s,d,n,k);
int reconstruct_partition(int s[],int d[MAXN+<span style="color:#][MAXN+<span style="color:#],int n,int k)
if(k==<span style="color:#)
print_books(s,<span style="color:#,n);
reconstruct_partition(s,d,d[n][k],k-<span style="color:#);
print_books(s,d[n][k]+<span style="color:#,n);
return <span style="color:#;
void print_books(int s[],int start,int end)
for(i=i&=i++)
printf(& %d &,s[i-<span style="color:#]);
printf(&\n&);
int main() {
int a[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
int b[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
printf(&first:\n&);
partition(a,<span style="color:#,<span style="color:#);
printf(&\nsecond:\n&);
partition(b,<span style="color:#,<span style="color:#);
return <span style="color:#;
工作量划分
这个问题被称为线性分割(linear partition)问题，有不少的应用情形。如，一系列任务分配给几个并行进程，那么分配工作量最大任务的那个进程将成为影响最终完成时间的瓶颈。将最大的工作量尽量减少，能够使所有工作更快地完成。
11.三次捡苹果
难度评级：★★★
（问题1的相关问题(1)的进一步扩展）一个矩形区域被划分为N*M个小矩形格子，在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，每经过一个格子就把其中的苹果全部拿走，最后到达(N,M)。此时，只允许向上或向左走一步，反方向走回(1,1)。这一趟可以不走第一趟的路线，但当经过第一趟所经过的格子时，里面已经没有苹果了。到达(1,1)后，再次反方向地只允许向右或向下走，走到(N,M)，同样可以不走前两趟走过的路线。求这三趟的走法，使得最终能拿取最多数量的苹果。
这个问题有两个难点，首先要理清三条路线的关系。可以发现，虽然第二趟方向相反，但其实和从(1,1)走到(N,M)是一样的，即三趟路线全部可以转化为从(1,1)向下或向右走到(N,M)的过程。
观察三条路线可以发现，实际中走的时候如果路线有交叉，可以把这种情况转化为相遇而不交错的情况如下图：
这样做的好处是，对于红线和蓝线上同一行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章贪心算法
《算法设计手册》第八章动态规划
《编程珠玑》相关问题
《编程之美》相关问题
附录1：其他的一些动态规划问题与解答（链接）
& 评：网络上的很多中文版本，都不如直接看这篇文章里的英文原版解答理解的清楚。
评：难度不高，注意要求的是空格数的立方和最小。
评：需要一些马尔科夫链的知识。理解起来不是很容易，理解以后是不是有种像是更多个生产线的装备线调度？
评：和0-1背包问题何其相似。
附录2：《算法设计手册》第八章 动态规划 面试题解答
给定一个硬币种类的集合，找出凑出给定一个值所用的最小硬币数目。
正文问题1已做解答，略。
长度为n的数组，其中元素可正可负可零。找出数组索引i,j使得从i到j的元素之和最大。
最大连续自序列和问题，请参考正文问题5的解答。
假设你有一页纸，正面和背面都写满了字母，当剪掉正面上一个字母时，这一页的背面的字母也会被剪掉。设计一个算法来验证是否能通过这张纸生成一个给定的字符串？提供一个函数，当你输入一个字母的位置时能够返回它背面的字母。（叙述关键思路即可）
目前我所看到的最容易理解的解法是使用最大流来解的：
下面把思路大意翻译一下。
假设需要拼成的字符串是&FOO&，同时这张纸的正反面对应位置上的内容（可以通过提供的函数获得）分别是：
由于位置4上的字母的正反面都用不到，忽略。
把这个表格转化成一个两层结点的流量网络
其中源点下面第一层表示拼成所需字符串的所有字母，源点到达该点的流量是需要的数目。第一层与第二层相连接表示某一位置上对应的是哪个所需字母，比如位置1正反面分别是F和O，表示它能提供1个F的入度和1个O的入度，但又由于一个片纸无论正反面只能用一次，那么它只能提供1的出度，直接连接汇点。
这个问题是否有解，等价于这个流量网络中是否存在一个流使得源点的流的出度等于汇点流的的入度，即一个最大流问题。
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！
