动态规划（Dynamic Programming）相关问题的一般形式是求最值，比如最长递增子序列等，动态规划的核心问题是【穷举】。因为在求最值的过程中，我们需要求出一系列可行的值，再从可行值之中选择出目标答案。
动态规划的 【穷举】 中，会产生很多很多重复计算，所以，我们可能需要一个“备忘录”保存重复计算的结果，同时，我们需要一个DP table来优化穷举的过程，记录子问题的结果，相关内容在递归算法篇章的斐波那契数列中见到过。
动态规划的三要素如下：
（1）重叠子问题，子问题的就算方式大致相同。
（2）复合最优子结构，问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。
（3）状态转移方程，怎么从子问题最优解推倒当前问题的最优解。
下面我们对经典的动态规划问题进行介绍~
一、最长递增子序列
题目： 给定一个无序的序列，求解它的【最长递增子序列】的长度。方法签名：int lengthOfLIS(int[] nums)。
注意：【子序列】和【子串】是不一样的，【子序列】是可以不连续的，但是子串必须是连续的。
举例： nums[] = {3,·1,4,1,5,9,2,6,5} 的最长递增子序列长度为4，结果返回4即可，此时的为子序列：1,4,5,9。
在使用【动态规划】方案解决该问题的时候，我们需要首先思考的是，怎么去设计一个dp数组，用来存放各个子问题的结果。
在这道题中，我们想：
（1）【宏观问题】是这个数组中存在的【最长子序列】。
（2）将其拆分成【子问题】就是，枚举出【从零到每一个位置】的最长递增序列，这也是我们所需要定义的一个dp数组。
（3）dp数组保存了所有的计算结果，最后在dp数组中找最值就可以了。
基于以上考虑，我们需要抽离一个共有的方法，就是【查找子序列】。
代码如下：
public class LengthOfLIS { public static void main(String[] args) { int i = lengthOfLIS(new int[]{1, 4, 2, 4, 6, 7, 8,4,23}); System.out.println(i); } public static int lengthOfLIS(int[] nums){ if(nums.length <= 0){ return 0; } int[] dp = new int[nums.length]; // 对给定数组进行逐一遍历，确定每个位置上的最长递增子序列 for (int i = 0; i < nums.length; i++) { // 先给dp数据当前位置初始化，因为最短的长度就是1 dp[i] = 1; // 确定当前的长度时，需要对前边已经计算的结果进行扫描 for (int j = 0; j < i; j++){ // 如果遇到比前边某一个位置的数字大，说明在之前的位置上，递增序列会被延长 if(nums[i] > nums[j]){ // 同时比较当前位置和最大子序列的长度，目的是取最大值 if(dp[i] < dp[j] +1){ dp[i] = dp[j] + 1; } } } } Arrays.sort(dp); return dp[dp.length-1]; } }
二、找零钱问题
题目： 给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名：int coinChange(int[] coins, int amount);（coins 中是可选硬币面值，amount 是目标金额）。
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。
首先，这个问题是【动态规划问题】，因为它具有【最优子结构】的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？
回到凑零钱问题，为什么说它符合最优子结构呢？
我们想知道总金额11需要最少几枚硬币，只需知道总结额为 10，9，6（总额减去一枚硬币面额的值）这几种情况下所需要的硬币的数量，然后找一个小的加1即可，这个过程是可以进行递归处理的，如下图：
重叠子问题： 当总额为0，1…amount时，分别最少需要多少枚硬币，因为当amount=0，时结果必为0。
符合最优子结构： 子问题amount所需硬币的最小值就是我们要的结果。
状态转移方程：
代码如下：
/** * 计算出能组成总金额的最少硬币数量 * @param coins 给定的硬币的面额 * @param amount 给定的总金额 * @return 最少的硬币数量 */ public static int coinChange(int[] coins, int amount){ if(amount == 0) return 0; if(amount < 0) return -1; // 核心： // 1、求总金额为16的结果 【1，3，5】 // 2、【1】找到15的最优解+1 ---- 【3】找到13的最优解+1 ----- 【5】找到11的最优解+1 // 3、取最小值 int result = Integer.MAX_VALUE; for (int i = 0; i < coins.length; i++) { int subMin = coinChange(coins, amount - coins[i]); // 如果最优解不存在 -1 继续 if (subMin == -1) continue; if(subMin + 1 < result){ result = subMin +1; } } return result == Integer.MAX_VALUE ? -1 : result; }
在此过程中，我们确实会出现很多的重复子问题计算，我们需要使用一个memo备忘录进行记录。
private static int changeCoin2(int[] coins,int amount,int[] memo){ if (amount == 0) return 0; if (amount < 0) return -1; int res = Integer.MAX_VALUE; for (int i = 0; i < coins.length; i++) { // 遍历子问题，假设amount为10元，如果有了一个2元，剩下的8元最少需要几个呢？，子问题就是8元所需要的个数 // 同理8元所需要的个数可以使用递归完成 int subProblem = Integer.MAX_VALUE; if(amount-coins[i] >= 0 && memo[amount-coins[i]] != 0){ subProblem = memo[amount-coins[i]]; } else { subProblem = changeCoin2(coins,amount-coins[i],memo); } // 子问题有误解的时候，比如子问题的金额小于硬币的最小金额 if(subProblem == -1) continue; // 我们的最优结果就是，最优的子问题的最优解+1 res = Math.min(res,1 + subProblem) != Integer.MAX_VALUE ? Math.min(res,1 + subProblem):-1; } memo[amount] = res; return res; }
最后比较一下有【备忘录】和没有【备忘录】的性能差异：
public class Change { ... public static void main(String[] args) { long start = System.currentTimeMillis(); System.out.println(changeCoin2(new int[]{1,2,3},100,new int[100+1])); long end = System.currentTimeMillis(); System.out.println(end - start); start = System.currentTimeMillis(); System.out.println(changeCoin(new int[]{1,2,3},100)); end = System.currentTimeMillis(); System.out.println(end -start); } }
三、0-1背包问题
题目： 有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
0-1背包问题： 在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中（背包中的该物品数为0或1），因此称为0-1背包问题。
子问题： 子问题必然是和物品有关的，对于每一个物品，有两种结果：能装下或者不能装下。
第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的。
第二，还有足够的容量装下该物品，但是装了不一定最大价值，所以要进行比较。由上述分析，子问题中物品数和背包容量都应当作为变量。
因此，子问题确定为背包容量为j时，求前i个物品所能达到最大价值。
确定状态： 由上述分析，“状态”对应的“值”即为背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0][0]为0，没有物品也就没有价值。
确定状态转移方程： 由上述分析，第i个物品的体积为w,价值为v，则状态转移方程为
f(n,v)={ f(n−1,v),weight[i]>j（装不下）
Math.max(f(i−1,j−weight[i])+value[i],f(i−1,j)),weight[i]<=j（可以装下）
我们很多时候，会看到为了解决这个问题会列出一个表格：
| 价值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 3 | 2 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 4 | 3 | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 | 7 | 7 |
| 5 | 4 | 0 | 0 | 3 | 3 | 5 | 7 | （3+5）8 | ||||
| 8 | 5 | 0 | ||||||||||
| 10 | 9 | 0 |
代码如下：
public class ZeroOnePackage { public static void main(String[] args) { int num = 5; //物品有五件 int capacity = 10; //背包容量为20 int[] weight = {2, 3, 4, 5, 9}; //重量 2 3 4 5 9 int[] value = {3, 4, 5, 8, 10}; //价值 3 4 5 8 10 int maxValue = zeroOnePackage(weight, value, num, capacity); System.out.println(maxValue); } public static int zeroOnePackage(int[] weight,int[] value,int num,int capacity) { // dp[i][j]意思是：背包容量为j时，在前i件物品中取小于等于i件物品，此时取得的物品的价值最大 // capacity为3时需要判断 0，1，2，3的最优解，所以二位数组的容量是capacity +1 int[][] dp = new int[num][capacity +1]; // 循环遍历，所有的物品 for (int i = 1; i < num; i++) { // 尝试获取 for (int j = 1; j <= capacity; j++) { // 如果重量比当前测试的包的容量的还大，必然装不下去 if (weight[i] > j) { // 当前的最优解就是之前的最优解 dp[i][j] = dp[i - 1][j]; } else { // 如果能放进去，先要腾出相应的空间，加上当前的重量的价值 // 然后对比上一个最优解，取最大的 // 拿：dp[i-1][j-weight[i]]+value[i] 不拿： dp[i-1][j] dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]); } } } return dp[num-1][capacity]; } }
完全背包（unbounded knapsack problem）与01背包不同就是每种物品可以有无限多个：一共有N种物品，每种物品有无限多个，第i（i从1开始）种物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
多重背包（bounded knapsack problem）与前面不同就是每种物品是有限个：一共有N种物品，第i（i从1开始）种物品的数量为n[i]，重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
