Baizer

Dynamic Programming 动态规划 ​

相关概念 ​

动态规划（Dynamic Programming） ​

维基百科：Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解为更小的子问题来求解问题的方法。是求解最优化问题的一种常用策略。

它主要用于解决具有“重叠子问题”和“最优子结构”性质的问题。

  • 重叠子问题：当一个问题可以分解为多个子问题，而这些子问题在解决过程中会重复出现。

  • 最优子结构：问题的最优解可以通过其子问题的最优解来构建。

使用步骤 ​

1、定义状态（状态是原问题、子问题的解）

  • 比如定义 dp[i] 的含义

2、设置初始状态（边界）

  • 比如设置 dp[0] 的值

3、确定状态转移方程

  • 比如确定 dp[i] 和 dp[i - 1]的关系

其难点是如何定义状态、确定状态转移方程，后续将通过大量的练习来举例。

  • 本质上是通过一个数组存储每个子问题的解，之后再通过这些子问题的解来推导全局的最优解
  • 自底向上，从算出小问题的最优解 -> 全局问题的最优解

贪心算法（Greedy） ​

贪心策略，也称为贪婪策略，每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解

  • 贪心策略并不一定能得到全局最优解

  • 因为一般没有测试所有可能的解，容易过早做决定，所以没法达到最佳解

  • 贪图眼前局部的利益最大化，看不到长远未来，走一步看一步

优点：简单、高效、不需要穷举所有可能，通常作为其他算法的辅助算法来使用

缺点：鼠目寸光，不从整体上考虑其他可能，每次采取局部最优解，不会再回溯，因此很少情况会得到最优解

示例问题：零钱兑换 ​

假设有 25 分、20 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？

贪心策略：每一次都优先选择面值最大的硬币

  1. 选择 25 分的硬币，剩 16 分
  2. 选择 5 分的硬币，剩 11 分
  3. 选择 5 分的硬币，剩 6 分
  4. 选择 5 分的硬币，剩 1 分
  5. 选择 1 分的硬币

得到的最终解为： 1枚25分、3枚5分、1枚1分的硬币，共5枚硬币

可实际上本题的最优解是（使用动态规划计算）：2枚20分、1枚1分的硬币，共3枚硬币

分治算法（Divide And Conquer） ​

分治，也就是分而治之，常用递归实现。

它的一般步骤是：

  • 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样）
  • 子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解）
  • 利用子问题的解推导出原问题的解

经典应用：快速排序、归并排序、二分查找、树、大整数乘法、最大连续子数组和

示例1：零钱兑换 ​

Leetcode原题：https://leetcode.cn/problems/coin-change/description/

假设有 25 分、20 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？

  • 此前用贪心策略得到的解为：（25、5、5、5、1），但并非是最优解
  • 最优解应该是：（20、20、1）

推导解题过程 ​

自底向上，逐渐累加金额，推断每个金额的最少找零次数（得到每个子问题的最优解）

  • dp[0] = 0（无需找零，初始化为0，为了给后续子问题递推使用）
  • dp[1] = 1（1元的最少找零次数为1，硬币面值：【1】）
  • dp[2] = 2（2元的最少找零次数为2，硬币面值：【1、1】）
  • dp[3] = 3（3元的最少找零次数为3，硬币面值：【1、1、1】）
  • dp[4] = 4（4元的最少找零次数为4，硬币面值：【1、1、1、1】）
  • dp[5] = 1（5元的最少找零次数为1，硬币面值：【5】）

① 定义状态（子问题的解）：假设dp[i]等于 i元的最少找零次数

  • i 表示金额，即从 0 到 amount 的值

② 设置初始状态（边界）：dp[0] =0

  • 0 元的最少找零次数自然为 0
  • 即初始化最小子问题的解为 0，后续子问题的解根据该初始值递推

③ 推断状态转移方程：dp[i] = Math.min(dp[i], dp[i - coin] + 1)

  • 如果i >= coin ，表示当前金额满足硬币面额找零（如果金额=3，硬币面额=5，即不满足最少找零金额，跳过本轮循环继续累加金额即可）
  • 尝试使用当前coin找零：
    • 先用金额扣减当前coin，得出一个剩余金额
    • 再获取这个剩余金额的最少找零次数，即dp[i - coin]
    • 在加上本轮的找零次数：+1，得出使用当前coin的最少找零次数
  • 再和默认找零次数dp[i]比较，二者取其最小值， 即最少找零次数（最优解）

状态转移方程详解：以i = 5为例子，即需要找零金额= 5时，代入公式dp[i - coin] + 1

  • 注意dp[5]默认初始化为 Integer.MAX_VALUE-1。

    • 其实只要比amount或者i大的值就行，例如amount+1

    • 但是如果使用了Integer.MAX_VALUE则需要-1， 因为要给下方预留一次找零次数，避免整数溢出。

  1. 选择面值【1】的硬币找零：dp[5 - 1] + 1 -> dp[4] + 1 = 5，即此时dp[5]最少找零次数为5

    • dp[i]= 5 = Math.min(Integer.MAX_VALUE-1, 5)

  2. 选择面值【5】的硬币找零：dp[5 - 5] + 1 -> dp[0] + 1 = 1，即此时dp[5]最少找零次数为1

    • dp[i]= 1 = Math.min(5, 1)
    • 此处会使用到dp[0]的值，所以开始时需要提前初始化。

遍历硬币面值【1、5、20、25】：在尝试不同的硬币面值的找零方案中，选择最少找零次数的方案，

  • 上述例子找零金额=5时，遍历了硬币面值【1、5】的找零方案，最终选择了使用【5】硬币找零，即最少找零次数的方案。

代码实现 ​

java
public int coinChange(int[] coins, int amount) {
    if(amount < 1 || coins == null || coins.length  == 0)  return -1;

    // ====== 初始化DP数组，用于存储子问题的解
    //存储每分钱需要找的最少硬币数量。例如 dp[10] 时，其值=2，即最少的找的零钱为 2 个 5 分钱硬币。
    int[] dp = new int[amount + 1];

    // ====== 设置初始状态，设置边界值
    // 填充 DP 数组每个值为最大金额
    Arrays.fill(dp, Integer.MAX_VALUE-1);
    dp[0] = 0; //初始化最小子问题的解为 0，以此递推

    // 遍历 amount，逐步累加 amount。（自底向上）
    // 获取每个子问题（dp[1]、dp[2]...）的最优解
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) { //遍历零钱面额数组
            if (i >= coin) {     //当金额累加支持找零时（例如，最小的零钱面值为5元，而金额只有4元时，则无需找零）

                // ===== 确定状态转移方程。
                // dp[i] = Math.min(dp[i], dp[i - coin] + 1); // 等效下方代码
                int current = dp[i];        // dp[i]为当前子问题的最优解，默认值为Integer.MAX_VALUE
                int remain  = dp[i - coin]; // 扣减coin零钱面值之后的子问题的最优解
                int newTime = remain + 1;   //扣减coin零钱面值的找零次数 + 本次找零 = 新的找零次数

                // 判断新的找零次数，是否小于当前i金额的找零次数
                if( newTime < current){
                    dp[i] = newTime; // 更新当前i金额的最少找零次数（也是当前金额的最优解）
                }
            }
        }
    }
    // 没有完整找零，返回-1
    if(dp[amount] == Integer.MAX_VALUE - 1) return -1;

    // dp[amount] 的最优解
    return dp[amount];
}

简洁版

java
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount+1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++){
        dp[i] = Integer.MAX_VALUE - 1;

        for (int coin : coins) {
            if(i >= coin){
                dp[i] = Math.min(dp[i],dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE - 1 ? -1 : dp[amount];
}

示例2：最大子数组和 ​

Leetcode原题：https://leetcode.cn/problems/maximum-subarray/description/

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  • 子数组是数组中的一个连续部分。

示例：nums = [-2,1,-3,4,-1,2,1,-5,4]

  • 即连续子数组 [4,-1,2,1] 的和最大，为 6 。

推导解题过程 ​

① 定义状态（子问题的解）：假设dp[i]等于 以nums[i]结尾的最大子连续数组之和

  • nums[0] = -2 结尾的最大子连续子数组是【-2】，其和dp[0] = -2
  • nums[1] = 1 结尾的最大子连续子数组是【1】，其和dp[1] = 1
  • nums[2] = -3 结尾的最大子连续子数组是【1、-3】，其和dp[2] = dp[1] + -3 = -2
  • nums[3] = 4 结尾的最大子连续子数组是【4】，其和dp[3] = 4
  • nums[4] = -1 结尾的最大子连续子数组是【4、-1】，其和dp[4] = dp[3] + -1 = 3
  • nums[5] = 2 结尾的最大子连续子数组是【4、-1、2】，其和dp[5] = dp[4] + 2 = 5
  • nums[6] = 1 结尾的最大子连续子数组是【4、-1、2、1】，其和dp[6] = dp[5] + 1 = 6

② 设置初始状态（边界）：dp[0]= nums[0]，即-2。

③ 推断状态转移方程

  • 如果dp[i - 1] <= 0，那么dp[i] = num[i]

    • dp[i - 1] 为上一个子问题的最优解，即上一个最大子连续子数组之和。
    • 如果小于等于0，即上一个最大子连续子数组之和是负数，那就没必要叠加。
    • 则当前子问题的最优解dp[i]，其最大和，=当前数组值num[i]即可。（参考nums[1]、nums[3]的情况）

  • 如果dp[i - 1] > 0，那么dp[i] = dp[i - 1] + num[i]

    • 即上一个最大子连续子数组之和是正数，那就必须要添加。（参考nums[2]、nums[4]、nums[5]、nums[6]的情况）
    • 因为状态定义要求是以nums[i]结尾的，所以即使num[i]值为负数，也需要添加。

最终的解从dp数组中选取最大值即可

代码实现 ​

java
public int maxSubArray(int[] nums) {
    if(nums == null || nums.length == 0) return 0;

    // 初始化DP数组，记录每个子问题的解
    int[] dp = new int[nums.length];

    // 设置初始值  dp[0] = -2
    dp[0] = nums[0];
    int maxSum = dp[0]; // 记录最大之和，默认为最小子问题的解

    //遍历数组，为每个元素求解
    for (int i = 1; i < nums.length; i++){
        // 定义状态：dp[i] = 以nums[i]结尾的最大子连续数组之和

        if(dp[i - 1] <= 0){
            // dp[i - 1] 为上一个子问题的最优解，即上一个最大子连续子数组之和。
            // 如果小于等于0，即上一个最大子连续子数组之和是负数，那就没必要叠加。
            // 则当前子问题的最优解 dp[i]，其最大和，=当前数组值 num[i]即可。(参考 i = 1、3 时)
            dp[i] = nums[i];
        }
        else{ // dp[i - 1] > 0
            // 即上一个最大子连续子数组之和是正数，那就必须要添加。(参考 i = 2、4、5、6 时)
            dp[i] = dp[i - 1] + nums[i];

        }
        // 最终的解从dp数组中选取最大值即可
        maxSum = Math.max(maxSum,dp[i]);
    }
    return maxSum;
}

因为 无需回溯所有子问题的解，只需要记录上一个子问题的最优解

dp数组可优化为dp变量，进一步降低空间复杂度 O(n) -> O(1)

java
/**
 * 优化空间复杂度 O(n) -> O(1)
 * @param nums
 * @return
 */
public int maxSubArray2(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    // 因为 无需回溯所有子问题的解，只需要记录上一个子问题的最优解
    // dp数组可优化为dp变量，进一步降低空间复杂度 O(n) -> O(1)
    int dp = nums[0];
    int max = dp;
    for (int i = 1; i < nums.length; i++) {
        if (dp > 0) {
            dp = dp + nums[i];
        } else {
            dp = nums[i];
        }
        max = Math.max(max, dp);
    }
    return max;
}

示例3：最长递增子序列（LIS） ​

又称：最长上升子序列（Longest Increasing Subsequence，LIS）

Leetcode原题：https://leetcode.cn/problems/longest-increasing-subsequence/description

给定一个无序的整数序列，求出它最长上升子序列的长度（要求严格上升）

  • 严格上升是指after值必须大于before值，不能等于或者小于。

示例：nums = [10,9,2,5,7,101,6]

  • 最长递增子序列是 [2,5,7,101] ，因此长度为 4

推导解题过程 ​

① 定义状态（子问题的解）：假设dp[i]等于 以nums[i]结尾的最长上升子序列的长度

  • 以nums[0] = 10结尾的最长上升子序列为【10】，其长度为 1，即 dp[0] = 1
  • 以nums[1] = 9 结尾的最长上升子序列为【9】，其长度为 1，即 dp[1] = 1
  • 以nums[2] = 2结尾的最长上升子序列为【2】，其长度为 1，即 dp[2] = 1
  • 以nums[3] = 5结尾的最长上升子序列为【2、5】，其长度为 2，即 dp[3] = dp[2] + 1 = 2
  • 以nums[4] = 7结尾的最长上升子序列为【2、5、7】，其长度为 3，即 dp[4] = dp[3] + 1 = 3
  • 以nums[5] = 101结尾的最长上升子序列为【2、5、7、101】，其长度为 4，即 dp[5] = dp[4] + 1 = 4
  • 以nums[6] = 6结尾的最长上升子序列为【2、5、6】，其长度为 3，即 dp[6] = dp[3] + 1 = 3

② 设置初始状态（边界）：dp[0]= 1

  • 并且所有dp[i]的值均默认为1，即自己就是最长序列

③ 推断状态转移方程：需遍历子问题的最优解

  • 如果 nums[i] <= nums[i - 1]，则不满足上升规则， dp[i]为默认值1
  • 如果 nums[i] > nums[i - 1]
    • 则表示当前nums[i]满足上升规则，可以拼接在nums[i - 1]后面形成一个长度更长的上升子序列
    • 更新dp[i]值为dp[i - 1] + 1
    • 因为需要遍历子问题的最优解，dp[i - 1]在代码实现中会改成dp[j]，另起一个变量用于内循环子问题

最终的解从dp数组中选取最大值（长度最长）即可

代码实现 ​

java
public int lengthOfLIS(int[] nums) {
    if(nums == null || nums.length == 0) return 0;

    // 初始化DP数组，存储每个子问题的最优解
    int[] dp = new int[nums.length];

    // 初始化最初解
    int max = dp[0] = 1; //默认长度都为1，即自己就是最长序列

    for (int i = 1; i < nums.length; i++){

        // dp[i] = 以 nums[i] 结尾的最长上升子序列的长度
        // 当前问题的最优解，默认值为1
        dp[i] = 1;

        //遍历子问题的最优解
        for (int j = 0; j < i; j++){
            int curValue = nums[i]; // 当前序列值
            int subValue = nums[j]; // 子序列值

            // 当前整数 大于 前一个整数时，表示满足上升规则，需要累加长度更新
            if( curValue > subValue ){

                //更新最长上升序列的长度，子问题的最优解（dp[j]） + 1
                // max是为了保证在内循环中也是最优解
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }
        //更新总问题的最优解， 及长度最长的上升子序列
        max = Math.max(dp[i],max);
    }
    return max;
}

简洁版

java
public int lengthOfLIS_Simple(int[] nums) {
    if(nums == null || nums.length == 0) return 0;

    int[] dp = new int[nums.length];
    int max = dp[0] = 1;

    for ( int i = 1; i < nums.length; i++){
        dp[i] = 1;
        for (int j = 0; j < i; j++){
            if(nums[i] > nums[j]){ // 当前序列值 大于 上一个子序列值
                dp[i] = Math.max( dp[j] + 1, dp[i] );
            }
        }
        max = Math.max( dp[i] , max );
    }
    return max;
}

示例4：0-1背包 ​

有一个背包，它的容量为C，以及n个物品。每个物品有一个重量w[i]和价值v[i]。你需要选择一些物品放入背包，使得背包的总重量不超过C，同时使得背包中的物品总价值最大。

  • 0-1 表示每件物品只能选择 0 件或者 1 件

假设背包的容量 C = 10，有 5 个物品，物品的重量和价值如下：

  • 物品 1：重量 w[1] = 2，价值 v[1] = 3
  • 物品 2：重量 w[2] = 3，价值 v[2] = 4
  • 物品 3：重量 w[3] = 4，价值 v[3] = 5
  • 物品 4：重量 w[4] = 5，价值 v[4] = 8
  • 物品 5：重量 w[5] = 9，价值 v[5] = 10

最大价值是: 15。

最优解是选择物品【2、4、1】，这些物品的总重量为 3 + 5 + 2 = 10，正好填满背包，总价值为 4 + 8 + 3 = 15。

推导解题过程 ​

① 定义状态（子问题的解）：假设dp[i][j]表示在i个物品中，能够达到背包容量j时，能获得的最大价值。

② 设置初始状态（边界）

  • dp[i][0] = 0 背包容量为0，不管有多少件物品都不放下，最大价值也为0
  • dp[0][j] = 0 0件物品，不管背包容量j多大，没有物品，最大价值都是0

③ 推断状态转移方程

外循环逐渐增加物品数量i，内循环逐渐增加背包容量j，再比较所有物品，挑选能放得下并且价值是最高的物品

  • weights[i]表示当前遍历的第i件物品的重量

  • 当 j < weights[i] 时，表示当前背包容量j放不下当前物品

    • 则dp[i][j] = dp[i - 1][j] ，表示当前容量的最大价值还是上一个物品的最大价值

  • 当 j >= weights[i] 时，表示当前背包容量j能放得下当前物品weights[i]。

    • 假设把当前物品放入背包：需要根据物品价值确定值不值得放。
      • 需用当前容量j扣减当前物品的重量weights[i]，得到一个 剩余容量
      • 再获取上一个物品中该剩余容量的最大价值 ，即dp[i - 1][j - weights[i]]
      • 得到剩余容量的 最大价值之后，再加当前物品的价值values[i]，得出当前背包的最大价值。
      • 再和上一个物品的最大价值比较dp[i - 1][j]，二者取其最大值，得出此轮内循环的最优解
    • 最终得出转移方程：dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weights[i]] + values[i]);

平铺DP数组，演示动态计算过程 ​

  • i表示物品件数，j表示背包容量
  • values物品价值，weights物品重量

初始化DP二维数组 ​

  • dp[i][0] = 0 背包容量为0，不管有多少件物品都不放下，最大价值也为0

  • dp[0][j] = 0 0件物品，不管背包容量j多大，没有物品，最大价值都是0

vwi / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
32i=000000000000
43i=10
54i=20
85i=30
109i=40

物品件数 i = 1 时 ​

递增背包容量 j，挑选能放得下并且价值是最高的物品

当前物品weights[i - 1]的重量为2（件数下标是从 0 开始，物品下标是从 1 开始，所以获取当前物品时需要 -1）

  • 当背包容量j = 1时，小于当前物品重量2，无法放入。
    • 根据状态转移方程，无法放入时取值上一个物品的最大价值
    • 即dp[i][j] = dp[i - 1][1]，等于dp[1][1] = dp[0][1] = 0
  • 当背包容量j >= 2时，均大于等于当前物品重量2，都可以放入。
    • 因为只有一件物品，此处不推演过程
    • 接取值当前物品价值即可：dp[1][2 ~ 10] = 3
vwi / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
32i=000000000000
43i=100333333333
54i=20
85i=30
109i=40

物品件数 i = 2 时 ​

递增背包容量 j，挑选能放得下并且价值是最高的物品

当前物品weights[i - 1]的重量为3，当前物品values[i - 1]的价值为4

  • 当背包容量j = 1时，小于当前物品重量3，无法放入。 当前dp[i][j]最大价值为0
  • 当背包容量j = 2时，小于当前物品重量3，无法放入。 当前dp[i][j]最大价值为0
  • 当背包容量j = 3时，等于当前物品重量3，可以放入。（需判断值不值得放）
    • 如果要放入当前物品，则需要先扣减当前物品容量，得到一个剩余容量，再去上一个物品中获取该剩余容量的最大价值
      • 上一个物品中该剩余容量的最大价值 + 当前物品的价值 = 本次放入物品的最大价值
      • 再把本次放入物品的最大价值和上一个物品的最大价值比较，选择其中最大值，得出当前子问题的最优解。
        • 如果取值上一个物品的最大价值是表示不放这件物品的情况
    • 带入数据：
      • 用当前容量3扣减当前物品的重量3，得到一个剩余容量0，获取上一个物品容量为0即dp[i-1][0]的最大价值为0
      • 剩余容量的最大价值0 + 当前物品的价值4 = 本次放入物品的最大价值4
      • 比较 本次放入物品的最大价值4 和 上一个物品的最大价值3，4 > 3，值得放
      • 选择放入当前物品，dp[i][j] = dp[2][3]值更新为4
vwi / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
32i=000000000000
43i=100333333333
54i=20004
85i=30
109i=40

  • 当背包容量j = 4时，大于当前物品重量3，可以放入。(判断是否值得放)

    • 用当前容量4扣减当前物品的重量3，得到一个剩余容量1，获取上一个物品容量为1即dp[i-1][0]的最大价值为0
    • 剩余容量的最大价值0 + 当前物品的价值4 = 本次放入物品的最大价值4
    • 比较 本次放入物品的最大价值4 和 上一个物品的最大价值3，4 > 3，值得放
    • 选择放入当前物品，dp[i][j] = dp[2][4]值更新为4
    vwi / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
    32i=000000000000
    43i=100333333333
    54i=200044
    85i=30
    109i=40
  • 当背包容量j = 5时，大于当前物品重量3，可以放入。(判断是否值得放)
    • 用当前容量5扣减当前物品的重量3，得到一个剩余容量2，获取上一个物品容量为2即dp[i-1][2]的最大价值为3
    • 剩余容量的最大价值3 + 当前物品的价值4 = 本次放入物品的最大价值7
    • 比较 本次放入物品的最大价值7 和 上一个物品的最大价值3，7 > 3，值得放
    • 选择放入当前物品，dp[i][j] = dp[2][5]值更新为7
vwi / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
32i=000000000000
43i=100333333333
54i=2000447
85i=30
109i=40

完整的推演表格 ​

vwi / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
32i=000000000000
43i=100333333333
54i=200044777777
85i=30034558991212
109i=4003458811121315

代码实现 ​

java
public int maxValue(int capacity, int[] values, int[] weights){
    if(values == null || weights == null) return 0;
    if(capacity <= 0 ||  values.length == 0 || weights.length == 0) return 0;
    if(values.length != weights.length) return 0;

    //物品数量，取值该数组长度即可
    int number = values.length;

    // ==== 定义状态：假设dp[i][j]表示在i个物品中，能够达到背包容量j时，能获得的最大价值。
    // 遍历物品时 i 从 1 开始，包含number，所以此处dp数组长度需要+1
    int[][] dp = new int[number + 1][capacity + 1];

    // ==== 设置初始值：int数组默认初始值为0
    // dp[0][0]是指0件物品或者0容量， 最大价值就是0，无处处理

    // 逐渐增加物品数量i，背包容量j，再遍历所有物品weights，挑选能放得下并且价值是最高的物品
    // 为了符合状态转移方程：dp[i - 1][j]，i必须从1开始，0开始会导致数组越界
    for (int i = 1; i <= number; i++){

        // 当前遍历的第i件物品的重量、价值（数组是0开始，所以需要-1）
        int curWeight = weights[i - 1];
        int curValue  = values[i - 1];

        for (int j = 1; j <= capacity; j++){

            //判断当前物品是否放得下（状态转移）
            if( j >= curWeight){

                // 放得下，挑选价值是最高的物品
                dp[i][j] = Math.max(

                        // j - curWeight = 剩余容量
                        // 取上一个物品[剩余容量]中的最大价值 + 当前物品的价值 = 放入当前物品后的最大价值
                        dp[i - 1][j - curWeight] + curValue,

                        // 取上一个物品 j 容量的最大价值， 用于比较值不值得放
                        dp[i - 1][j]
                );
            }else{
                // 放不下，那就不放了，用上一件物品的最优解即可
                dp[i][j] = dp[i - 1][j];
            }

        }
    }

    return dp[number][capacity];
}

简洁版本

java
public int maxValue(int capacity, int[] values, int[] weights){
    if(values == null || weights == null) return 0;
    if(capacity <= 0 ||  values.length == 0 || weights.length == 0) return 0;
    if(values.length != weights.length) return 0;

    int number = values.length;
    int[][] dp = new int[number + 1][capacity + 1];

    for (int i = 1; i <= number; i++){
        int curWeight = weights[i - 1];
        int curValue  = values[i - 1];
        
        for (int j = 1; j <= capacity; j++){
            if(j >= curWeight){
                dp[i][j] = Math.max(
                        dp[i - 1][j - curWeight] + curValue,
                        dp[i - 1][j]
                );
            }else{
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[number][capacity];
}

代码实现：优化为一维数组 ​

vwi / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
32i=000000000000
43i=100333333333
54i=200044777777
85i=30034558991212
109i=4003458811121315

观察推演表格可以发现，dp[i][j] 只依赖于 dp[i - 1][j] 和 dp[i - 1][j - weights[i - 1]]，也就是说，dp[i][j] 只需要前一行的信息。

  • 例如dp[4][10]=dp[3][10] or (dp[3][5] + values[4])

因此不需要保存每一行的所有状态，只需要保存前一个行所有背包容量的的最大价值即可。

  • 通过变更内循环的方向，即倒序更新状态（j--）
  • 从背包容量的最大值开始遍历到当前物品的重量

一维表格倒序推演（从右往左） ​

每叠加一件物品，本论循环的dp解刚好不会覆盖上轮循环的解

i / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
i=000333333333
i / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
i=100344777777
i / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
i=20034578991212
i / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
i=3003458811121315
i / jj=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10
i=4003458811121315

代码实现 ​

  • 定义状态：dp[j] 来表示背包容量 j 时的最大价值。
  • 状态转移方程：dp[j] = Math.max(dp[j],dp[j - weights[i]] + values[i])
java
public int maxValueOptimization(int capacity, int[] values, int[] weights){
    if(values == null || weights == null) return 0;
    if(capacity <= 0 ||  values.length == 0 || weights.length == 0) return 0;
    if(values.length != weights.length) return 0;


    int number = values.length;
    // dp[j] 来表示背包容量 j 时的最大价值。
    int[] dp = new int[capacity + 1];

    // i不需要在dp数组中使用，不会涉及转移方程的运算，只在物品数组中使用，所以正常从0开始即可
    for (int i = 0; i < number; i++){

        // 当前遍历的第i件物品的重量、价值
        int curWeight = weights[i];
        int curValue  = values[i];

        // 从背包容量的最大值开始遍历到当前物品的重量（倒序更新状态）
        // j >= weights[i] 表示放得下才进入本次循环
        for (int j = capacity; j >= weights[i]; j--){

            // int answer = dp[j];         //默认值为0
            // int remain = j - curWeight; // 剩余容量
           dp[j] = Math.max(
                   dp[j],
                   // 取dp[剩余容量]中的最大价值 + 当前物品的价值 = 放入当前物品后的最大价值
                   // dp[j - curWeight]，由于是倒序更新，该值默认都是0
                   dp[j - curWeight] + curValue
           );
        }
    }
    return dp[capacity];
}

简洁版

java
public int maxValueOptimization(int capacity, int[] values, int[] weights){
    if(values == null || weights == null) return 0;
    if(capacity <= 0 ||  values.length == 0 || weights.length == 0) return 0;
    if(values.length != weights.length) return 0;

    int number = values.length;
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < number; i++){
        int curWeight = weights[i];
        int curValue  = values[i];

        for (int j = capacity; j >= weights[i]; j--){
            dp[j] = Math.max(
                    dp[j],
                    dp[j - curWeight] + curValue
            );
        }
    }
    return dp[capacity];
}

参考 ​