前言

动态规划和贪心算法类似，但是又有所区别。

贪心算法是由局部最优解，推导出全局最优解。

动态规划也是局部最优解，但是无法通过局部最优解推导全局最优解。

案例

案例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)

用表格具象的表示：

编写代码：

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));
}