动态规划概述

一、知识储备

【重叠子问题】

分治法将问题分解成若干个相互独立的子问题，但一个问题分解所得的子问题并不总是相互独立的，它们可能共享更小的子问题

如果采用递归的分治法求解，势必要重复计算这些共享子问题。

如下面是计算斐波那契数列的分治算法，它将Fib(n)的计算分解为两个较小的问题：计算Fib(n-1)和计算Fib(n-2)，两者之和就是Fib(n)。

从上图中我们可以看到许多子问题被重复计算。

而动态规划法正是利用了这种子问题的重叠性质，自底向上对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解，这样就可以避免重复计算这些重叠子问题。

两种方法的代码如下：

/*	递归求解	*/ 
int f(int n)
{
	if(n==1||n==0) return 1;
	else return f(n-1)+f(n-2);
}
int main()
{
	int n;
	cin>>n;
	cout<<f(n);
}

/*	DP求解		*/ 
int save[100];
int f(int n)
{
	if (save[n]!=0) 
		return save[n];
	if (n==1||n==0){ 
		save[n]=1; 
		return save[n]; 
	}
	save[n]= f(n-1)+f(n-2);
	return save[n]; 
}
int main()
{
	memset(save,0,sizeof(save));
	int n;
	cin>>n;
	cout<<f(n);
}

提示：计算F(n)是以计算它的两个重叠子问题F(n-1)和F(n-2)的形式来表达的，所以上面的DP求解过程中可以设计一张表填入n+1个F(n)的值。

动态规划法求解斐波那契数F(9)的填表过程：

【最优子结构特性】

问题的最优解中包含了子问题的最优解

【状态】

我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。

二、动态规划法基本知识

定义：一种求解最优化问题的算法设计策略。

实质：将较大问题分解为较小的同类子问题（这一点与分治法和贪心法类似）+ 记忆化搜索

用DP求解的问题具有以下特征：

能够分解为相互重叠的若干子问题
具有最优子结构特性

设计动态规划算法的步骤：

分段：将原问题分解为若干个相互重叠的子问题；
分析：分析问题是否具有最优子结构特性，并找出动态规划函数的递推式；
求解：利用递推式自底向上计算，实现动态规划过程。

动态规划法的设计思想：

动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。

求解问题过程：

动态规划法采用分步决策的方式求解问题。动态规划每一步的决策依赖于子问题的解，为了在某一步上做出选择，需要先求解若干子问题，再根据子问题的解做出决策，这就使得动态规划法求解问题的方法是自底向上的。

换种说法，动态规划法利用问题的最优子结构特性，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。

好处：

问题的规模越大，用动态规划的好处就越明显地体现出来
填完整个表，得到题目所求，花的时间要大大快于不填表递归的求解所花时间
设题目的规模为n，分治法时间复杂度为O（2ⁿ），而动态规划法的时间复杂度仅为O（n²）

与贪心法的区别

动态规划法先求子问题的解，然后通过求解子问题构造原问题的解；贪心算法是直接地解原问题。
动态规划法通过对若干局部最优解的比较，去掉了次优解，从而产生了更高一层次的局部最优解。相当于对较低层次的局部最优解进行贪心的选择而得到高一级的局部最优解，因而最终产生一个最高层次的局部最优解。贪心法每阶段只作一个挑选，各阶段的解一经选出就固定不变了，后阶段的局部最优是基于前阶段的挑选，所以往往只能求出次优解。

与分治法的区别

共同点：把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。
不同点：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。

其他

动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要求解一个给定的问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
动态规划问题满足三大重要性质
最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

三、借助题目加深理解

【题目一】

首先，肯定得用二维数组a[][]来存放数字三角形

然后我们用a[ i ][ j ] 来表示第 i 行第 j 个数字(i, j从1开始算)

我们用sum(i , j)表示从a[ i ][ j ]到底边的各条路径中，最佳路径的数字之和。

因此，此题的最终问题就变成了求sum(1,1)。

当我们看到这个题目的时候，首先想到的就是可以用简单的递归来解题：

从a[ i ][ j ]出发，下一步只能走a[ i+1 ][ j ]或者a[ i+1 ][ j+1 ]。

故对于N行的三角形，我们可以写出如下的递归式：

if ( i == N)               
    sum(i,j) = a[i][j];
else     
    sum(i,j) = max{sum(i+1,j),sum(i+1,j+1)} + a[i][j];

根据上面这个简单的递归式，我们就可以很轻松地写出完整的递归代码：

#include<iostream>
using namespace std;
#define maxn 100
int a[maxn][maxn];
int sum(int i,int j,int n)
{
	if( i==n ) return a[i][j];
	else 
	{
		if (sum(i+1,j,n)>sum(i+1,j+1,n))
			return	sum(i+1,j,n)+a[i][j];
		else 
			return 	sum(i+1,j+1,n)+a[i][j];
	}    
}
int main()
{
	int i,j,t;
	int n;
	cin>>n;
	for (i=0;i<n;i++)
		for(j=0;j<=i;j++)
			cin>>a[i][j]; 
	cout<<sum(0,0,n);
}

显而易见，这个算法就是最简单的搜索算法。因为存在大量重复计算，所以时间复杂度为2ⁿ，明显是会超时的。

分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，我们提出了记忆化搜索：

我们存放一个opt数组，Opt[ i ][ j ] - 每产生一个sum(i, j)，将sum(i, j)的值放入opt中，以后再次调用到sum(i, j)的时候，直接从opt[ i ][ j ]来取就可以了。

于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度：

#include<iostream>
using namespace std;
#define maxn 100
int a[maxn][maxn];
int opt[maxn][maxn];
int sum(int i,int j,int n)
{
	if (opt[i][j]!=0)	return opt[i][j];
	if( i==n ) 
	{ 
		opt[i][j]=a[i][j];
		return a[i][j];	
	}
	else 
	{    
		opt[i+1][j]=sum(i+1,j,n);
		opt[i+1][j+1]=sum(i+1,j+1,n);
		if (opt[i+1][j] > opt[i+1][j+1])
			return  opt[i+1][j]+a[i][j];
		else 
			return 	opt[i+1][j+1]+a[i][j];
	}    
}
int main()
{
	int i,j,t;   
	int n;
	cin>>n;
	memset(opt,0,sizeof(opt));
	for (i=0;i<n;i++)
		for(j=0;j<=i;j++)
			cin>>a[i][j]; 
	cout<<sum(0,0,n);
}

【题目二】

/*计算组合数的动态规划算法*/
int combinat(int m,int n)
{
	int i,j;
	int mat[1000][1000];
	if(n==0||m==n)	return 1;
	for(j=0;j<n;j++)
	{
		mat[0][j]=1;
		for(i=1;i<=m-n;i++)
			if (j==0) 
				mat[i][j]=i+1;
			else 
				mat[i][j]=mat[i-1][j]+mat[i][j-1];
	}            			 	/* 计算Cmn */
	return (mat[m-n][n-1]);   /* 返回计算结果 */
}

四、基于实例讲解动态规划算法

【动态规划】

基于一个递推公式及一个或多个初始状态
当前子问题的解将由上一次子问题的解推出

【入门】

首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。

状态：用来描述该问题的子问题的解

例子：

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候。)

首先我们思考一个问题，如何用最少的硬币凑够i元(i<11)？为什么要这么问呢？两个原因：1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。 2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

好了，让我们从最小的i开始吧。当i=0，即我们需要多少个硬币来凑够0元。由于1，3，5都大于0，即没有比0小的币值，因此凑够0元我们最少需要0个硬币。 (这个分析很傻是不是？别着急，这个思路有利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。”会比较方便，如果一直用纯文字来表述，不出一会儿你就会觉得很绕了。

那么，我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。当i=1时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够0元即可，而这个是已经知道答案的，即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。当i=2时，仍然只有面值为1的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到这里，你都可能会觉得，好无聊，感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币！耐心点，让我们看看i=3时的情况。当i=3时，我们能用的硬币就有两种了：1元的和3元的( 5元的仍然没用，因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬币有两种，我就有两种方案。如果我拿了一个1元的硬币，我的目标就变为了：凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。这个方案说的是，我拿3个1元的硬币；第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 这个方案说的是，我拿1个3元的硬币。好了，这两种方案哪种更优呢？记得我们可是要用最少的硬币数量来凑够3元的。所以，选择d(3)=1，怎么来的呢？具体是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。

OK，码了这么多字讲具体的东西，让我们来点抽象的。从以上的文字中，我们要抽出动态规划里非常重要的两个概念：状态和状态转移方程。

上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的"状态"，这个状态是怎么找出来的呢？我在另一篇文章动态规划之背包问题(一)中写过：根据子问题定义状态。你找到子问题，状态也就浮出水面了。最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币。那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。没错，它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下：d(i)=min{ d(i-v_j)+1 }，其中i-v_j >=0，v_j表示第j个硬币的面值。

有了状态和状态转移方程，这个问题基本上也就解决了。

伪代码：

下图是当i从0到11时的解：

从上图可以得出，要凑够11元至少需要3枚硬币。

此外，通过追踪我们是如何从前一个状态值得到当前状态值的，可以找到每一次我们用的是什么面值的硬币。比如，从上面的图我们可以看出，最终结果d(11)=d(10)+1(面值为1)，而d(10)=d(5)+1(面值为5)，最后d(5)=d(0)+1 (面值为5)。所以我们凑够11元最少需要的3枚硬币是：1元、5元、5元。

注意：原文中这里本来还有一段的，但我反反复复读了几遍，大概的意思我已经在上文从i=0到i=3的分析中有所体现了。作者本来想讲的通俗一些，结果没写好，反而更不好懂，所以这段不翻译了。

【初级】

上面讨论了一个非常简单的例子。现在让我们来看看对于更复杂的问题，如何找到状态之间的转移方式(即找到状态转移方程)。为此我们要引入一个新词叫递推关系来将状态联系起来(说的还是状态转移方程)

OK，上例子，看看它是如何工作的。

一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LIS：longest increasing subsequence)

正如上面我们讲的，面对这样一个问题，我们首先要定义一个“状态”来代表它的子问题，并且找到它的解。注意，大部分情况下，某个状态只与它前面出现的状态有关，而独立于后面的状态。

让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“状态转移方程”。假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度，其中i<N，那么上面的问题变成了原问题的一个子问题(问题规模变小了，你可以让i=1,2,3等来分析) 然后我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。OK，对照“入门”中的简单题，你应该可以估计到这个d(i)就是我们要找的状态。如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。状态找到了，下一步找出状态转移方程。

为了方便理解我们是如何找到状态转移方程的，我先把下面的例子提到前面来讲。如果我们要求的这N个数的序列是：

5，3，4，8，6，7

根据上面找到的状态，我们可以得到：（下文的最长非降子序列都用LIS表示）

前1个数的LIS长度d(1)=1(序列：5)
前2个数的LIS长度d(2)=1(序列：3；3前面没有比3小的)
前3个数的LIS长度d(3)=2(序列：3，4；4前面有个比它小的3，所以d(3)=d(2)+1)
前4个数的LIS长度d(4)=3(序列：3，4，8；8前面比它小的有3个数，所以 d(4)=max{d(1),d(2),d(3)}+1=3)

OK，分析到这，我觉得状态转移方程已经很明显了，如果我们已经求出了d(1)到d(i-1)，那么d(i)可以用下面的状态转移方程得到：

d(i) = max{1, d(j)+1}，其中j<i,A[j]<=A[i]

用大白话解释就是，想要求d(i)，就把i前面的各个子序列中，最后一个数不大于A[i]的序列长度加1，然后取出最大的长度即为d(i)。当然了，有可能i前面的各个子序列中最后一个数都大于A[i]，那么d(i)=1，即它自身成为一个长度为1的子序列。

分析完了，上图：(第二列表示前i个数中LIS的长度，第三列表示LIS中到达当前这个数的上一个数的下标，根据这个可以求出LIS序列)

代码：

#include <iostream>
using namespace std;

int lis(int A[], int n){
    int *d = new int[n];
    int len = 1;
    for(int i=0; i<n; ++i){
        d[i] = 1;
        for(int j=0; j<i; ++j)
            if(A[j]<=A[i] && d[j]+1>d[i])
                d[i] = d[j] + 1;
        if(d[i]>len) len = d[i];
    }
    delete[] d;
    return len;
}
int main(){
    int A[] = {
        5, 3, 4, 8, 6, 7
    };
    cout<<lis(A, 6)<<endl;
    return 0;
}

该算法的时间复杂度是O(n² )，并不是最优的解法。还有一种很巧妙的算法可以将时间复杂度降到O(nlogn)，网上已经有各种文章介绍它，这里就不再赘述。传送门： LIS的O(nlogn)解法。此题还可以用“排序+LCS”来解，感兴趣的话可自行Google。

练习题：

无向图G有N个结点(1<N<=1000)及一些边，每一条边上带有正的权重值。找到结点1到结点N的最短路径，或者输出不存在这样的路径。

提示：在每一步中，对于那些没有计算过的结点，及那些已经计算出从结点1到它的最短路径的结点，如果它们间有边，则计算从结点1到未计算结点的最短路径。

尝试解决以下来自topcoder竞赛的问题：

ZigZag – 2003 TCCC Semifinals 3
BadNeighbors – 2004 TCCC Round 4
FlowerGarden – 2004 TCCC Round 1

【中级】

接下来，让我们来看看如何解决二维的DP问题。

平面上有N＊M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来，这样下去，你最多能收集到多少个苹果。

解这个问题与解其它的DP问题几乎没有什么两样。第一步找到问题的“状态”，第二步找到“状态转移方程”，然后基本上问题就解决了。

首先，我们要找到这个问题中的“状态”是什么？我们必须注意到的一点是，到达一个格子的方式最多只有两种：从左边来的(除了第一列)和从上边来的(除了第一行)。因此为了求出到达当前格子后最多能收集到多少个苹果，我们就要先去考察那些能到达当前这个格子的格子，到达它们最多能收集到多少个苹果。 (是不是有点绕，但这句话的本质其实是DP的关键：欲求问题的解，先要去求子问题的解)

经过上面的分析，很容易可以得出问题的状态和状态转移方程。状态S[i][j]表示我们走到(i, j)这个格子时，最多能收集到多少个苹果。那么，状态转移方程如下：

S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)

其中i代表行，j代表列，下标均从0开始；A[i][j]代表格子(i, j)处的苹果数量。

S[i][j]有两种计算方式：1.对于每一行，从左向右计算，然后从上到下逐行处理；2. 对于每一列，从上到下计算，然后从左向右逐列处理。这样做的目的是为了在计算S[i][j]时，S[i-1][j]和S[i][j-1]都已经计算出来了。

伪代码如下：

以下两道题来自topcoder，练习用的。

AvoidRoads – 2003 TCO Semifinals 4
ChessMetric – 2003 TCCC Round 4

【中高级】

这一节要讨论的是带有额外条件的DP问题。

以下的这个问题是个很好的例子。

无向图G有N个结点，它的边上带有正的权重值。

你从结点1开始走，并且一开始的时候你身上带有M元钱。如果你经过结点i，那么你就要花掉S[i]元(可以把这想象为收过路费)。如果你没有足够的钱，就不能从那个结点经过。在这样的限制条件下，找到从结点1到结点N的最短路径。或者输出该路径不存在。如果存在多条最短路径，那么输出花钱数量最少的那条。限制：1<N<=100 ; 0<=M<=100 ; 对于每个i，0<=S[i]<=100；正如我们所看到的，如果没有额外的限制条件(在结点处要收费，费用不足还不给过)，那么，这个问题就和经典的迪杰斯特拉问题一样了(找到两结点间的最短路径)。在经典的迪杰斯特拉问题中，我们使用一个一维数组来保存从开始结点到每个结点的最短路径的长度，即M[i]表示从开始结点到结点i的最短路径的长度。然而在这个问题中，我们还要保存我们身上剩余多少钱这个信息。因此，很自然的，我们将一维数组扩展为二维数组。M[i][j]表示从开始结点到结点i的最短路径长度，且剩余j元。通过这种方式，我们将这个问题规约到原始的路径寻找问题。在每一步中，对于已经找到的最短路径，我们找到它所能到达的下一个未标记状态(i,j)，将它标记为已访问(之后不再访问这个结点)，并且在能到达这个结点的各个最短路径中，找到加上当前边权重值后最小值对应的路径，即为该结点的最短路径。 (写起来真是绕，建议画个图就会明了很多)。不断重复上面的步骤，直到所有的结点都访问到为止(这里的访问并不是要求我们要经过它，比如有个结点收费很高，你没有足够的钱去经过它，但你已经访问过它) 最后Min[N-1][j]中的最小值即是问题的答案(如果有多个最小值，即有多条最短路径，那么选择j最大的那条路径，即，使你剩余钱数最多的最短路径)。

伪代码：

下面有几道topcoder上的题以供练习：

Jewelry – 2003 TCO Online Round 4
StripePainter – SRM 150 Div 1
QuickSums – SRM 197 Div 2
ShortPalindromes – SRM 165 Div 2

【高级】

以下问题需要仔细的揣摩才能将其规约为可用DP解的问题。

问题：StarAdventure – SRM 208 Div 1:

给定一个M行N列的矩阵(M*N个格子)，每个格子中放着一定数量的苹果。你从左上角的格子开始，只能向下或向右走，目的地是右下角的格子。你每走过一个格子，就把格子上的苹果都收集起来。然后你从右下角走回左上角的格子，每次只能向左或是向上走，同样的，走过一个格子就把里面的苹果都收集起来。最后，你再一次从左上角走到右下角，每过一个格子同样要收集起里面的苹果 (如果格子里的苹果数为0，就不用收集)。求你最多能收集到多少苹果。

注意：当你经过一个格子时，你要一次性把格子里的苹果都拿走。

限制条件：1 < N, M <= 50；每个格子里的苹果数量是0到1000(包含0和1000)。

如果我们只需要从左上角的格子走到右下角的格子一次，并且收集最大数量的苹果，那么问题就退化为“中级”一节里的那个问题。将这里的问题规约为“中级”里的简单题，这样一来会比较好解。让我们来分析一下这个问题，要如何规约或是修改才能用上DP。首先，对于第二次从右下角走到左上角得出的这条路径，我们可以将它视为从左上角走到右下角得出的路径，没有任何的差别。 (即从B走到A的最优路径和从A走到B的最优路径是一样的)通过这种方式，我们得到了三条从顶走到底的路径。对于这一点的理解可以稍微减小问题的难度。于是，我们可以将这3条路径记为左，中，右路径。对于两条相交路径(如下图)：

在不影响结果的情况下，我们可以将它们视为两条不相交的路径：

这样一来，我们将得到左，中，右3条路径。此外，如果我们要得到最优解，路径之间不能相交(除了左上角和右下角必然会相交的格子)。因此对于每一行y( 除了第一行和最后一行)，三条路径对应的x坐标要满足：x1[y] < x2[y] < x3[y]。经过这一步的分析，问题的DP解法就进一步地清晰了。让我们考虑行y，对于每一个x1[y-1]，x2[y-1]和x3[y-1]，我们已经找到了能收集到最多苹果数量的路径。根据它们，我们能求出行y的最优解。现在我们要做的就是找到从一行移动到下一行的方式。令Max[i][j][k]表示到第y-1行为止收集到苹果的最大数量，其中3条路径分别止于第i,j,k列。对于下一行y，对每个Max[i][j][k] 都加上格子(y,i)，(y,j)和(y,k)内的苹果数量。因此，每一步我们都向下移动。我们做了这一步移动之后，还要考虑到，一条路径是有可能向右移动的。 (对于每一个格子，我们有可能是从它上面向下移动到它，也可能是从它左边向右移动到它)。为了保证3条路径互不相交，我们首先要考虑左边的路径向右移动的情况，然后是中间，最后是右边的路径。为了更好的理解，让我们来考虑左边的路径向右移动的情况，对于每一个可能的j,k对(j<k)，对每个i(i<j)，考虑从位置(i-1,j,k)移动到位置(i,j,k)。处理完左边的路径，再处理中间的路径，最后处理右边的路径。方法都差不多。

用于练习的topcoder题目：

MiniPaint – SRM 178 Div 1

【其它】

当阅读一个题目并且开始尝试解决它时，首先看一下它的限制。如果要求在多项式时间内解决，那么该问题就很可能要用DP来解。遇到这种情况，最重要的就是找到问题的“状态”和“状态转移方程”。(状态不是随便定义的，一般定义完状态，你要找到当前状态是如何从前面的状态得到的，即找到状态转移方程)如果看起来是个DP问题，但你却无法定义出状态，那么试着将问题规约到一个已知的DP问题(正如“高级”一节中的例子一样)。

五、DP思想带来的问题

动态规划分类有很多划分方法，网上有很多是按照状态来分，分为一维、二维、区间、树形等等。

我觉得还是按功能即解决的问题的类型以及难易程度来分比较好，下面按照我自己的理解和归纳，把动态规划的分类如下：

一、简单基础dp

这类dp主要是一些状态比较容易表示，转移方程比较好想，问题比较基本常见的。主要包括递推、背包、LIS（最长递增序列），LCS（最长公共子序列），下面针对这几种类型，推荐一下比较好的学习资料和题目。

1、递推：

递推一般形式比较单一，从前往后，分类枚举就行。

简单:

hdu 2084 数塔简单从上往下递推

hdu 2018 母牛的故事简单递推计数

hdu 2044 一只小蜜蜂... 简单递推计数（Fibonacci）

hdu 2041 超级楼梯 Fibonacci

hdu 2050 折线分割平面找递推公式