day 36 第九章 动态规划part04

第一题：1049. 最后一块石头的重量 II

解题思路

1. 整体思路与转化为 01 背包问题的思路

本题可以通过巧妙的思路转化为 01 背包问题来求解。核心想法是要使得最后剩下石头的重量最小，我们可以把所有石头的总重量分成两堆尽量接近的石头堆（想象成把这些石头分别装进两个虚拟的 “背包”），然后用总重量减去这两堆石头重量和的差值（也就是较大堆减去较小堆），就能得到最后剩下石头的最小重量了。

具体来说，先算出所有石头重量的总和 sum，目标就是找到一种划分方式，让两堆石头重量尽可能接近 sum / 2（这里使用 sum >> 1 相当于 sum / 2 的效果，并且位运算效率更高些），这个 sum / 2 就相当于背包的容量，而每块石头就相当于 01 背包里的物品，每个物品（石头）只有选或者不选两种情况，放入其中一堆石头（一个 “背包”）里，然后通过动态规划求出在这个 “容量” 限制下能装的最大重量，进而算出最后剩下石头的最小重量。

2. 动态规划过程分析

• 计算总和与目标值：
  首先通过循环 for(int i : stones) 累加数组 stones 中所有元素的值得到总和 sum，然后计算出目标值 target（也就是 sum / 2 的近似值，这里用位运算 sum >> 1），这个 target 就是我们后续动态规划中当作背包容量来考虑的数值。

• 创建动态规划数组并初始化（隐式边界条件）：
  创建一个长度为 target + 1 的一维数组 dp，其中 dp[j] 表示在容量为 j 的情况下（类比于挑选石头重量累加和的大小），能得到的最大石头重量和。初始时数组元素默认都是 0，表示还没有开始挑选石头时，任何容量下能达到的和都是 0，这也是一种边界情况的初始化，相当于背包里什么都没装的时候，重量为 0。

• 动态规划核心计算（两层循环）：

  • 外层循环：通过 for 循环遍历数组 stones 的每个元素，相当于依次考虑每一块 “石头” 是否要放入 “背包”（也就是选择放进某一堆石头里）。每次循环针对当前的石头 stones[i] 去尝试更新不同 “容量”（也就是不同累加和情况）下能达到的最大石头重量和。
  • 内层循环：内层循环从目标容量 target 开始，倒序遍历到当前石头 stones[i] 的大小。倒序的原因和普通 01 背包问题中内层循环倒序一样，是为了保证每个 dp[j] 的更新是基于上一轮（也就是还没考虑当前石头 stones[i] 加入选择时）的状态值，避免重复选择和错误的数据覆盖，符合 01 背包问题一维优化的要求。在循环中，根据状态转移方程 dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]) 来更新 dp[j] 的值，其含义是：对于当前的 “容量” j，有两种情况决定最大石头重量和，一是不选择当前的第 i 块石头，此时最大石头重量和就是之前在 “容量” j 下已经计算出的最大石头重量和 dp[j]（也就是上一轮循环结束后的状态值）；二是选择当前的第 i 块石头，那么石头重量和就要加上该石头的重量 stones[i]，同时 “容量” 要减去该石头所占的 “空间”（也就是 stones[i]），所以对应的最大石头重量和就是 dp[j - stones[i]] + stones[i]（dp[j - stones[i]] 是上一轮在剩余 “容量” 下能达到的最大石头重量和），然后取这两种情况中的较大值作为新的 dp[j]，通过这样不断循环更新，逐步推导出在考虑完所有石头后，不同 “容量” 下所能获得的最大石头重量和。

• 剪枝与返回结果：
  在每次外层循环结束（也就是每考虑完一块石头后），都检查一下 dp[target] 是否已经等于 target 了，如果等于，那就说明已经找到了一种划分方式，使得其中一堆石头的重量和刚好达到了目标值（尽可能接近总和的一半），此时就可以提前结束计算，直接返回 sum - 2 * dp[target] 作为最后剩下石头的最小重量。如果整个外层循环结束后都没有出现这种情况，那就最后再返回 sum - 2 * dp[target]，这个值就是通过两堆石头重量尽可能接近 sum / 2 的思路，算出的最后剩下石头的最小重量。

代码

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i : stones){
            sum += i;
        }
        int target = sum >>1;
        //初始化dp数组
        int[] dp = new int[target + 1];
        for(int i = 0;i < stones.length;i++){
            //采用倒序遍历
            for(int j = target;j >= stones[i];j--){
                dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
            }
            //剪枝
            if(dp[target] == target){
                return sum - 2 * dp[target];
            }
        }
        return sum - 2 * dp[target];
    }
}

第二题： 494. 目标和

解题思路

1. 问题转化思路

本题可以通过巧妙的数学思维转化为 01 背包问题来求解。

我们把数组 nums 中的元素想象成物品，每个元素有两种选择，要么前面添加 “+” 号，要么添加 “-” 号，这就类似 01 背包里物品的取或不取。假设所有添加 “+” 号的元素之和为 left，添加 “-” 号的元素之和为 right，那么根据题意有 left - right = target，同时又知道 left + right = sum(nums)（也就是数组所有元素的总和）。

通过联立这两个等式可以推导出 left = (target + sum(nums)) / 2，这样问题就转化为了：从数组 nums 中挑选若干元素，使得它们的和等于 left（也就是 (target + sum(nums)) / 2），有多少种不同的挑选方法，这就与 01 背包问题的形式相符了，即从给定的物品集合里选择部分物品凑出特定的 “容量”（这里的 “容量” 就是 left 的值），求组合的数量。

2. 可行性判断

• 首先，通过循环 for(int i = 0;i < nums.length;i++) 计算数组 nums 所有元素的总和 sum。
• 然后进行两个可行性判断：
  • 如果 target 的绝对值大于 sum，那显然是不可能通过添加 “+”“-” 号构造出等于 target 的表达式的，因为就算所有元素都添加 “+” 号（也就是最大情况了），也达不到 target 的值，所以直接返回 0。
  • 如果 (target + sum) 除以 2 的余数不为 0，这意味着按照前面推导的逻辑，无法找到满足条件的 left 值（因为 left 应该是个整数呀），同样不存在满足要求的构造表达式的方案，也返回 0。

3. 动态规划过程

• 确定背包 “容量” 与初始化动态规划数组：
  计算出背包 “容量” bageSize，也就是 Math.abs((target + sum) / 2)，创建长度为 bageSize + 1 的一维数组 dp，其中 dp[j] 表示凑出和为 j 的表达式的数量。将 dp[0] 初始化为 1，这是因为有一种情况是啥都不选（也就是所有元素前面都添加 “-” 号，相当于和为 0 的一种特殊情况），所以凑出和为 0 的表达式数量初始就是 1 种，这是一个边界情况的初始化。

• 动态规划核心计算（两层循环）：

  • 外层循环：通过 for 循环遍历数组 nums 的每个元素，相当于依次考虑每一个 “物品”（也就是数组中的每个数）是否要用来凑出目标和（也就是放入 “背包” 来增加 “容量”）。
  • 内层循环：内层循环从背包 “容量” bageSize 开始，倒序遍历到当前元素 nums[i] 的大小。倒序遍历的原因和常规 01 背包问题中内层循环倒序一样，是为了保证每个 dp[j] 的更新是基于上一轮（也就是还没考虑当前元素 nums[i] 加入选择时）的状态值，避免重复计算和错误的数据覆盖，符合 01 背包问题一维优化的要求。在循环中，根据状态转移方程 dp[j] += dp[j - nums[i]] 来更新 dp[j] 的值，其含义是：对于当前的 “容量” j，要凑出和为 j 的表达式数量（dp[j]），可以分为两种情况，一种是不选择当前的第 i 个元素，那么表达式数量就是之前已经计算出的 dp[j]（也就是上一轮循环结束后的状态值）；另一种是选择当前的第 i 个元素，此时就相当于要在剩余 “容量”（j - nums[i]）下凑出和，而之前在剩余 “容量” 下凑出和的表达式数量就是 dp[j - nums[i]]，所以把这两种情况对应的表达式数量相加，就得到了更新后的 dp[j] 的值，通过这样不断循环更新，逐步推导出在考虑完所有元素后，不同 “容量”（也就是不同目标和）下所能构造出的表达式的数量。

• 返回结果：
  当两层循环结束后，dp[bageSize] 就表示能凑出和为 bageSize（也就是前面推导出的 left 的值）的表达式数量，也就是能构造出运算结果等于 target 的不同表达式的数目，将其返回就是本题的答案。

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
        }
        //如果target的绝对值大于sum，那么是没有方案的
        if(Math.abs(target) > sum) return 0;
        //如果（target+sum）除以2的余数不为0，也是没有方案的
        if((target + sum) % 2 != 0) return 0;
        int bageSize = Math.abs((target+sum) / 2);
        int[] dp = new int[bageSize + 1];
        dp[0] = 1;
        //遍历nums数组
        for(int i = 0;i < nums.length;i++){
            for(int j = bageSize;j >= nums[i];j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bageSize];
    }
}

第三题：474.一和零

解题思路

1. 问题识别与转化为背包问题思路

本题可以看作是一个二维的 01 背包问题。我们可以把 m 个 0 和 n 个 1 分别看作是两种 “背包容量”，而数组 strs 中的每个二进制字符串就是 “物品”。每个字符串有一定数量的 0 和 1，就相当于物品有相应的 “重量”（这里是两种维度的 “重量”，对应 0 的个数和 1 的个数），并且每个字符串只能选择一次（类似 01 背包里物品只能取 0 次或 1 次），目标是在给定的两种 “背包容量”（m 个 0 和 n 个 1）限制下，找出能装进背包的 “物品”（字符串）数量最多的情况，也就是求满足条件的最大子集的长度。

2. 动态规划过程

• 创建并初始化动态规划数组：
  创建一个二维数组 dp，大小为 [m + 1][n + 1]，其中 dp[i][j] 表示在最多可以使用 i 个 0 和 j 个 1 的情况下，所能得到的最大子集长度。初始时，整个 dp 数组的值都默认为 0，这相当于还没有往 “背包” 里装任何 “物品”（字符串）时的初始状态，表示最大子集长度为 0。

• 遍历字符串数组并统计 0 和 1 的个数：
  通过外层循环 for (String str : strs) 依次遍历输入的二进制字符串数组 strs 中的每个字符串。对于每个字符串 str，使用内层循环 for (char ch : str.toCharArray()) 来统计该字符串中 0 的个数 zeroNum 和 1 的个数 oneNum。这一步就是在获取每个 “物品”（字符串）的两种 “重量”（0 和 1 的数量）信息，为后续放入 “背包” 做准备。

• 动态规划核心计算（两层嵌套循环更新 dp 数组）：

  • 外层循环倒序遍历 i（对应 0 的数量维度的背包容量）：
    从 m 开始倒序遍历到当前字符串中 0 的个数 zeroNum，这里倒序遍历的原因和一维 01 背包问题中内层循环倒序的道理类似，是为了保证每个 dp[i][j] 的更新是基于上一轮（也就是还没考虑当前字符串加入选择时）的状态值，避免重复选择和错误的数据覆盖，确保每个字符串只被考虑一次，符合背包问题的要求。
  • 内层循环倒序遍历 j（对应 1 的数量维度的背包容量）：
    从 n 开始倒序遍历到当前字符串中 1 的个数 oneNum，同样是基于避免重复选择和错误覆盖的考虑。在这个两层嵌套循环中，根据状态转移方程 dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1) 来更新 dp[i][j] 的值，其含义是：对于当前的两种 “背包容量”（i 个 0 和 j 个 1），有两种情况决定最大子集长度，一是不选择当前的这个字符串，此时最大子集长度就是之前在同样 “背包容量”（i 个 0 和 j 个 1）下已经计算出的最大子集长度 dp[i][j]（也就是上一轮循环结束后的状态值）；二是选择当前的这个字符串，那么子集长度就要加 1（表示选择了一个新的字符串加入子集），同时 “背包容量” 要分别减去该字符串中 0 和 1 的个数（也就是变成 i - zeroNum 个 0 和 j - oneNum 个 1），所以对应的最大子集长度就是 dp[i - zeroNum][j - oneNum] + 1（dp[i - zeroNum][j - oneNum] 是上一轮在剩余 “背包容量” 下能达到的最大子集长度），然后取这两种情况中的较大值作为新的 dp[i][j]，通过这样不断循环更新，逐步推导出在考虑完所有字符串后，不同 “背包容量”（不同的 i 和 j 值）下所能获得的最大子集长度。

• 返回最终结果：
  当两层嵌套循环结束，也就是考虑完数组 strs 中的所有字符串后，dp[m][n] 就表示在最多可以使用 m 个 0 和 n 个 1 的情况下，所能得到的最大子集长度，将其返回就是本题的答案。

代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (String str : strs) {
            int oneNum = 0,zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            //倒序遍历dp数组，确保每个字符串只被考虑一次
            for(int i = m;i >=zeroNum;i--){
                for(int j = n;j >= oneNum;j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
}