介绍
动态规划（Dynamic programming，简称 DP）常常适用于有重叠子问题和最优子结构性质的问题.
递归树中重复计算产生了重叠子问题而引入了备忘录，动态规划最优子结构是通过求子问题的最优解，可以得到原问题的最优解（一般求max min等）
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量
核心思想是把一个复杂的大问题拆成若干个子问题，通过解决子问题来逐步解决大问题
动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是
分治策略一般用于解决子问题相互独立的情况，一般用递归实现；而动态规划则用于解决子问题有重叠的情况，既可以用递归备忘录实现，也可以用动态规划迭代实现
0-1背包
这里通过经典的0-1背包问题来深化动态规划的思想：现在有一个背包它的容量为C(C=5)，现在有n(n=3)种物品,物品的重量weight = [1,2,3]。每件物品的价值为value = [6,10,12]。问可以在这个背包中装哪些物品，在不超过背包容量的前提下总价值最大。每一件物品可放进背包也可不放，求解最大价值？
方案一：递归（备忘录）
为自顶向下的递归实现，这里bestValue递归方法存在子问题重叠问题（重复计算），采用类似缓存的思想：将先前解决的子问题，进行存储，以减少重复计算！ 这就是带备忘录的递归解决方法
private int[][] memery;
//w重量 v价值 C容量
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
memery = new int[n][C + 1]; //初始化为 -1
for(int i = 0; i < n; i ++)
for(int j = 0; j <= C; j ++)
memery[i][j] = -1;
return bestValue(w, v, n - 1, C); //从n-1选择开始 到0
}
// 用 [0...index]的物品,填充容积为c的背包的最大价值
private int bestValue(int[] w, int[] v, int index, int c){
if(c <= 0 || index < 0)
return 0;
if(memery[index][c] != -1)
return memery[index][c];
int res = bestValue(w, v, index-1, c); //不取当前index的物品价值
if(c >= w[index]) //能装入前提下（这很重要） 两个最大价值（取当前index的物品价值）
res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
return memery[index][c] = res;
}
方案二：动态规划
自下而上的迭代方式，在解决动态规划的问题上最重要的是状态的定义和状态转移方程
这里分3步来解决：
状态是什么，这里就是我们dp函数的定义，一般用一维数组或者二维数组。我们定义一个二维数组 int[][] dp = new int[n][C + 1]，这里表示0到n个商品，0到C容量下所有的状态的解。从小的问题迭代循环推出大的问题的答案，最后就可以通过返回dp[n - 1][C]就是我们要的答案
状态转移方程，也就是找出数组元素之间的关系式，我觉得动态规划，有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了
这里的状态转移方程应该是：dp[i][j] = Math.max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]) (j >= w[i])在选择第i件物品的时候,如果当前容量j装得下，那么比较不选第i件物品dp[i - 1][j]和选择第i件物品（选择了容量要减小价值变大）这两种情况的价值，取较大值。相反如果装不下，就直接等于dp[i - 1][j] 第i件物品不选，容量不变继续选择下一件物品。找出初始值边界值,也就是最简单的问题的dp解，这样有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值，这里通过转移方程可以看到选择第i物品的结果只依赖于前面第i-1物品的结果（dp数组后一行依赖于前一行的结果，所有在这里我们初始化第一行的数据即可，也就是先算出只有一件商品的dp数组值）
通过上面递归的方式就会很容易写出相应DP方式的状态转移方程，往往递归方式是容易理解的，不妨在想不出来动态规划的状态转移方程的时候，先通过递归求解问题。
往往在草稿纸上可以用较小数据量来试着推导出DP数组每个元素结果，更直观更容易优化理解。如下图：
代码如下：时间复杂度O(nC) 其中n为物品个数,C为背包容积。空间复杂度O(nC)
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
int[][] dp = new int[n][C + 1];
//初始化第一行
for(int i = 0; i <= C; i++) {
//装第一个物品 未知容量 的最大价值
if (i >= w[0]) { //当前容量能装下第一个物品
dp[0][i] = v[0];
} else {
dp[0][i] = 0;
}
}
//是否选择第i件物品
for(int i = 1; i < n; i++) {
for (int j = 0; j <= C; j++) {
if (j >= w[i]) {
//当前容量能装下第i件物品 取两者最大值 第i件选与不选
dp[i][j] = Math.max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
} else {
// 装不下 只能继续看下一件
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n - 1][C];
}
优化
如上图可以看到每一行的结果只依赖上一行的结果，那么在此我们可以优化空间大小，把二维矩阵 dp 优化成 一维矩阵的 dp。每次迭代推导的时候只需更新这一行数组即可。
时间复杂度O(n*C)不变，空间复杂度: O(C), 只使用了C的额外空间
通常大多数情况下画出二维 dp 的矩阵图，然后看元素之间的值依赖，然后就可以很清晰看是否可以优化
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
//优化了空间
int[] dp = new int[C + 1]; //只使用一维数组
//初始化第一行 不变
for(int i = 0; i <= C; i++) {
//装第一个物品 未知容量 的最大价值
if (i >= w[0]) { //当前容量能装下第一个物品
dp[i] = v[0];
} else {
dp[i] = 0;
}
}
for(int j = 1; j < n; j++) {
//是否选择第j件物品 i >= w[j]就提前停止，dp[i]不变 还是原先的dp[i]
for(int i = C; i >= w[j]; i--) { //注意 从大到小逆推 如果从小到大，会影响索引大的dp结果
dp[i] = Math.max(dp[i], v[j] + dp[i - w[j]]);
}
}
return dp[C];
}