动态规划是一种非常常见的算法，但是在学习算法很久以后才理解什么是动态规划，因为动态规划实在是"名不副实"，从名称上很难直观地对算法有个认识。要说动态规划，还得从分治法说起。

分治法

分治法几乎学过程序的人都能理解，简而言之就是分而治之，一个问题很复杂很难解决，就设法把大问题转化为若干个小问题，小问题解决后再经过汇总，大问题也就迎刃而解了。

举个例子，在某公司，要设计开发一个大型项目，上百人一窝蜂去解决这个问题效率显然很低，这时CTO会把项目分解成若干子项目，分给各部门总监，总监拿到项目又进行模块分解，分给手下的各个小组，由各个小组负责开发完成具体的模块，在总监指导下完成整合，再由CTO汇总在一起，就合理地分工完成一个大型的项目了。这就是分治法。

那动态规划跟分治法有什么关系呢？再看上面的例子，当各个小组负责开发时，发现有些模块是重复的！比如网络框架，如果各个小组各自为战，每个小组都会开发一套自己的网络框架，这显然会造成大量的人员浪费。CTO考虑到这点，就会想，为什么不构建一个所有小组都能通用的公共库呢？当一个小组开发完成一个功能，就放入公共库，其他小组再开发前，先在公共库查找，如果已经有了，就不用再开发了，这就节省了大量的重复工作。

其中用一个公共的"Table"记录已经完成的工作，避免重复运算，这种解决问题的思路，就是动态规划了。

动态规划

现在就知道什么是动态规划了。动态规划类似于分治法，适用于子问题相互重叠的场景，动态规划使用一个table保存计算结果，确保每个子问题只被运算一次。

动态规划被用于解决"最优解"问题。举上面的例子，如果CTO不知道如何分配任务，想知道由哪个小组做哪个模块才能最快，需要进行多次"尝试"，把问题的各种分配方法都试一次，让各小组解决，看如何分配才能最快，这显然其中有很多重复的开发，但如果把某个小组执行某个模块需要多长时间都记录下来，可以最大程度上减少开发。（注意这里的问题已经不是解决这个项目了，而是怎么分解项目能达到最优解，table里存的变成某个小组完成某个模块的时间，求最优解往往要比求一个解复杂很多），这就是求最优解的应用了。

解题步骤

现在对动态规划有了一个感性的认识，接下来需要看看面对具体的问题该如何解决了，先看看动态规划通用的解题方法。

  • 分析最优解特征
  • 递归定义最优解
  • 自底向上求解
  • 构造最优解

这只是一个抽象的步骤，接下来通过动态规划一个典型的应用"背包问题"来说明一下具体是如何实现的。

0-1背包问题

题目

有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

分析最优解特征

如果每件物品只有一件，就是典型的0-1背包问题，这里先来看看0-1背包问题如何解决。感性地认识一下题目，每个物品只有放入背包和不放入背包两种选择，如果先挑单体重量价值最大的，也有可能体积太大无法装下其他货物，还不如放两个价值不是最大的划算，乍一看还是挺难解决的。接下来使用动态规划详细分析一下题目。

首先什么是一个解，就是一种背包方法，解的值就是背包中物品的最大价值。最优解就是不同的取法中最大的价值。再来看看这个最优解的递归特征，所谓的递归特征，就是如何把大问题化为小问题。这里考虑把N件物品转化为N-1件物品，考虑最后一件物品（索引从0开始）：c[N-1], w[N-1]，只有两种可能：不放入背包和放入背包。如果最优解中没有物品obj(N-1)，那么最优解其实就是N-1个物品的最优解；如果obj(N-1)存在最优解中，那么也可以把这个问题转换为N-1个物品的最优解，只是背包的容量就剩下V-c[N-1]了。这样不论哪种情况，都可以把N个物品的问题，转化为N-1个物品的问题。这就是最优解的递归特性。

递归定义最优解

分析完递归特性以后，便很容易定义一个递归公式。记f(i, j)为把前i件物品放入容量为j的背包能获得的最大价值：

	f(i, j) = max{ f(i-1, j), f(i-1, j-c[i]) + w[i] }      其中 j >= c[i]
	f(i, j) = f(i-1, j)                                      其中 j < c[i]

i=0时没有物品，f(0, j) = 0。N=1只有一个物品的时候很容易解决，直接看能不能放下即可；N>1的时候，想办法利用最优解的递归特性转换为N-1，使我们解决的问题少了一个维度，这是解决这类问题的关键。

其实如果学过数学归纳法，会发现这个思路很相似，数学归纳法是已知f(0)成立，要证明f(N-1)成立的情况下f(N)成立，解题关键是怎么推导f(N-1)到f(N)。这里的递归结构同理，已知f(0)，要想办法从f(N-1)的解推出f(N)的解。

自底向上求解

公式有了，只要用程序实现即可。这里的自底向上，是指从0到N逐个求解，因为公式本身具有递归特性，所以用递归解决这个问题最为直接：

	int Package(int N, int c[], int w[], int V)
	{
		int w_contain = 0;
		int w_without = 0;
		
		if (N == 1 && c[0] <= V) {
			return w[0];
		}
		if (N == 1 && c[0] > V) {
			return 0;
		}
		
		w_without = Package(N-1, c, w, V);
		w_contain = Package(N-1, c, w, V - c[N-1]) + w[N-1];
		if (w_contain > w_without) {
			return w_contain;
		}
		else {
			return w_without;
		}
	}

那说了半天，动态规划怎么还没用呢？接下来可以看一下这个代码的复杂度，很容易能看出来，每次代码都会走两个分支，复杂度是 O(2^n)，指数级别的复杂度很大，如果n很大的情况下，代码就不具有可行性了。那如何优化呢，这就需要动态规划了。保存什么结果呢？可以看出其中的N和V都是变量，所以需要以这两个为key存储最优解。代码就优化为：

	int table[N][V] = {};
	
	int init()
	{
		for (int i = 0; i < V * N; i++) {
			table[i] = -1;
		}
	}
	
	int Package(int N, int c[], int w[], int V)
	{
		int w_contain = 0;
		int w_without = 0;
		
		if (N == 1 && c[0] <= V) {
			return w[0];
		}
		if (N == 1 && c[0] > V) {
			return 0;
		}
		
		/* 当前子问题已经计算过，直接返回 */
		if (table[N-1][V] != -1) {
			return table[N-1][V];
		}
		
		w_without = Package(N-1, c, w, V);
		
		if (V >= c[N-1]) {
			w_contain = Package(N-1, c, w, V - c[N-1]) + w[N-1];
		}
		
		table[N-1][V] = (w_contain > w_without) ? w_contain : w_without;
		return table[N-1][V];
	}

经过动态规划的优化，因为table表里的值最多计算一次，时间复杂度变成O(NV)，当然也增加了O(NV)的空间复杂度，是典型的用空间换时间的做法。

空间优化

如果仔细考虑一下，会发现其实空间还可以进一步优化，因为计算过程中，f(N)依赖于f(N-1)，并不依赖于N-1之前的结果，完全可以在计算过程中，使f(N)覆盖掉f(N-1)的结果，节省空间。

	int table[V] = {};
	
	void Package(int N, int c[], int w[], int V)
	{
		for (int i = 0; i < N; i++) {
			for (int j = V; j >= c[i]; j--) {
				int w_contain = table[j-c[i]] + w[i];
				int w_without = table[j];
				table[j] = (w_contain > w_without) ? w_contain : w_without;
			}
		}
	}

因为需要一层一层计算，所以递归代码改成了迭代。内层循环必须从大到小倒序遍历，这样才能保证计算table[j]时用到的table[j-c[i]]还是上一层（i-1）的结果。空间复杂度缩小至O(V)，时间复杂度仍然是O(N*V)。

构造最优解

解了半天，终于能知道最大能背多少价值的东西了，但是如何取才能得到最优解呢？通过空间优化的方法计算，已经没法得知怎么才能是最优解了，因为计算的过程已经被抹杀了。但是使用非空间优化的方法，很容易获取，只需要把最优解table[N-1][V]是怎么计算出来的倒推回去即可。

	int table[N][V] = {};
	
	void ConstructResult(int N, int c[], int w[], int V)
	{
		for (int i = N-1; i >= 1; i--) {
			if (V >= c[i] && table[i-1][V] < table[i-1][V-c[i]] + w[i]) {
				printf("1\t");
				V -= c[i];
			}
			else {
				printf("0\t");
			}
		}
		/* 最后剩下第 0 件物品，看剩余容量是否足够 */
		printf(c[0] <= V ? "1\n" : "0\n");
	}

按照刚才计算的过程倒推回去，便可知道如何取才能得到最优解。只是按照这种方法打印出来的是倒序，需要调整一下顺序。

有界背包问题

问题

刚才只是最简单的一种背包问题，0-1背包，其中一个物品只有一个。如果再加一个条件，一个物品可以有有限多个，这个问题就变成了有界背包问题（通常也称为多重背包问题）。对于有界背包问题如何解决呢？

算法

其实有界背包问题可以很容易转换为0-1背包问题，如果一个物品可以选择n次，只需要把一个物品重复n个，就成了n个物品的0-1背包问题。通过动态规划便可顺利解决了。

无界背包问题

如果把0-1背包的问题再变化一下，每种物品可以无限选择，就不能用有界背包的解法把问题转换为0-1背包了（通常也称为完全背包问题）。当然可以借用0-1背包的思路，0-1背包在递归的时候会考虑存在和不存在的情况，从而把问题转换为N-1的子问题，而无界背包问题同样可以考虑这个物品不出现、出现1次、2次……等多种情况，把问题降维到N-1。只是要比0-1背包复杂好多。

事实上还有一个更巧妙的转换：借用空间优化一节的滚动数组思路，0-1背包内层循环是倒序遍历，保证每件物品只被使用一次；如果把内层循环改为从小到大正序遍历，计算table[j]时用到的table[j-c[i]]已经是本层（i）的结果，就相当于物品可以被重复选取，这就得到了完全背包的解法。

另外，动态规划还有一些其他应用，比如最长公共子序列，可以进一步学习动态规划的应用。