基本思想

动态规划的主要思想：将复杂的问题拆分成一步步可以简单实现的子问题，每一步的子问题要利用之前已经解决的子问题求解，所以需要记录下每一步解决子问题的结果，需要时候进行查表就好。

例子：背包问题

问题描述：

假设我们有n种类型的物品，分别编号为1, 2…n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是Cap。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？注意：每种物品只有一件，可以选择放或者不放。

问题分析

我们要直接暴力求解n个物品的最大价值很难，但如果我们退一步，求解n-1个物品呢？看起来似乎简单点，但依旧很难，那如果我们把它取到极限，只有1种物品，这时候就会发现简单很多！！那么在得到1种物品的基础上，求放2种物品的方案是不是也很简单，以此类推，直到求出n种物品的解决方案。算法代码如下：

#include<vector>
using namespace std;

vector<vector<int>> bag(int n, int* w, int* v, int c){//n是物品种类数，w是物品重量，v是物品价值，c是容量
	vector<vector<int>> res(n+1, vector<int>(c+1, 0)); //存储最佳结果,+1是为了计算方便
	for(int i=1;i<n+1;i++){//i表示第几种物品
		for(int j=1;j<c+1;j++){//j表示容量
			res[i][j] = res[i-1][j];
			if(j>=w[i-1]){//判断当前重量
				if(res[i-1][j-w[i-1]]+v[i-1] > res[i][j]){//判断最大价值
					res[i][j] = res[i-1][j-w[i-1]]+v[i-1];
				}
			}
		}
	}
	return res;
}