前言
动态规划和贪心算法类似，但是又有所区别。
贪心算法是由局部最优解，推导出全局最优解。
动态规划也是局部最优解，但是无法通过局部最优解推导全局最优解。
案例
案例1
比如有此题目-来源力扣
若一个字符串中，'L' 和 'R' 字符的数量是相同的，那称该字符串为平衡字符串。
请将一个平衡字符串分隔成尽可能多的子字符串，并满足子字符串也是平衡字符串。
如：
输入：s = "RLRRLLRLRL" 输出：4 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R'
此时便可以用贪心算法：遍历字符串，遇到一个平衡字符串就直接记录下来，并将后续的字符串当做新的平衡字符串处理
局部最优解，推导出全局最优解
代码
public int balancedStringSplit(String s) { int count = 0; int cur = 0; char[] chars = s.toCharArray(); for (char c : chars) { if(c == 'R'){ cur++; }else { cur--; } if(cur == 0){ count++; } } return count; }
案例2
现有一格子大小为5的背包，有三样物品，它们的价值和所占的格子分别为
- 物品1：价值1500，占格子数1
- 物品2：价值2000，占格子数3
- 物品3：价值3000，占格子数4
需要你求将这些物品放入背包的最大价值是多少？
如果此时使用贪心算法解决：
局部最优：背包格子为1格时的最大价值
全局最优：先取1格容量装入物品，剩下的容量当做新背包处理。
此时得出的最大价值为：1500 + 2000 = 3500，而最大价值应为4500
那么此类问题便是要由动态规划方式解决了。
动态规划
动态规划特点：
- 局部最优解：也就是它会有一个最优子结构
- 子问题可以重复
- 状态转移方程：通过把问题分成很多小阶段一段段的转移。从而得出最优解.
动态规范问题的最关键便是：状态转移方程，可以说我们能写出状态转移方程，那动态规划问题基本上就解决了一大半。
以案例2为例子
设f(i,n)为背包占格子数为n时放入i物品的最大价值 —— 局部最优解
那么当放入一个占格子数为m物品i时，此时会发生两种情况
- m <= n 可以放下该物品，f(i,n) = i_value(i物品的价值) + f(i-1, n-m) 剩余背包大小(n-m)放入物品i-1时的最大价值
- m > n f(i,n) = f(i-1,n)上一个物品(i-1)在背包大小为n时的价值
但m <= n还有一种情况，即为f(i-1,n)大于i_value + f(i-1, n-m)
所以总结为：
- m <= n f(i,n) = Math.max(i_value + f(i-1, n-m), f(i-1,n))
- m > n f(i,n) = f(i-1,n)
用表格具象的表示：
| 物品、格子 | 1 | 2 | 3 | 4 | 5 |
| 物品1 | 1500 | 1500 | 1500 | 1500 | 1500 |
| 物品2 | 1500(放不下) | 1500(放不下) | 2000 | 3500 | 3500 |
| 物品3 | 1500(放不下) | 1500(放不下) | 2000(放不下) | 3500(>3000) | 4500 |
编写代码：
public int dp(int[] value, int[] size, int bagSize){ // 当为物品i，背包n时的最大价值 int[][] dp = new int[value.length+1][bagSize+1]; for (int i = 1; i <= value.length; i++) { // 遍历背包的格子，计算当格子大小为n时的最大价值 for (int n = 1; n <= bagSize; n++) { // 当前物品所占格子数 int m = size[i-1]; if(m <= n){ // 放得下 // f(i,n) = Math.max(i_value + f(n-m), f(i-1,n)) dp[i][n] = Math.max(value[i-1] + dp[i-1][n-m], dp[i-1][n]); }else { // f(i,n) = f(i-1,n) dp[i][n] = dp[i-1][n]; } } } return dp[dp.length-1][dp[0].length-1]; } public static void main(String[] args) { System.out.println(dp(new int[]{1500, 2000, 3000}, new int[]{1,3,4}, 4)); System.out.println(dp(new int[]{1500, 2000, 3000}, new int[]{1,3,4}, 5)); System.out.println(dp(new int[]{10, 20, 50}, new int[]{1,2,4}, 5)); System.out.println(dp(new int[]{6, 10, 12}, new int[]{1,2,4}, 5)); }
