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

分治法

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

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

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

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

动态规划

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

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

解题步骤

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

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

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

0-1背包问题

题目

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

分析最优解特征

如果题目中N件物品都只有一件，就是典型的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个物品的问题。这就是最优解的递归特性。

递归定义最优解

分析完递归特性以后，便很容易定义一个递归公式：

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;
	}
	
	w_without = table[N-1][V];
	if (w_without == -1) {
		w_without = Package(N-1, c, w, V);
		table[N-1][V] = w_without;
	}
	
	w_contain = table[N-1][V - c[N-1]];
	if (w_contain == -1) {
		w_contain = Package(N-1, c, w, V - c[N-1]) + w[N-1];
		table[N-1][V - c[N-1]] = w_contain;
	}
	
	return (w_contain > w_without) ? w_contain : w_without;
}

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

空间优化

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

int table[V] = {};

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

因为需要一层一层计算，所以递归代码改成了迭代。空间复杂度缩小至O(V)，时间复杂度仍然是O(N*V)。

构造最优解

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

int table[N][V] = {};

bool result[N] = {};

void ConstructResult(int N, int c[], int w[], int V)
{
	for (int i = N-1; i >=0; i++) {
		if (table[i-1][V] > table[i-1][V-c[i]] + w[i]) {
			printf("1\t");
			V -= w[i];
		}
		else {
			printf("0\t");
		}
	}
	print("\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背包复杂好多。

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