代码随想录算法训练营打卡Day43 | LeetCode1049 最后一块石头的重量 II、LeetCode494 目标和、LeetCode474 一和零

摘要

• 用动态规划解决问题时，不仅要从简单的子问题来考虑递推公式，也要从问题的整体来考虑，看问题的输入参数本身有什么性质和公式，也有助于得到递推公式。

LeetCode1049 最后一块石头的重量 II

1049. 最后一块石头的重量 II - 力扣（Leetcode）

• 从问题的整体来考虑，要使一堆石头两两一起“粉碎”后剩余的重量值最小，那么应该把这堆石头尽可能地分成重量相等或相近的两堆石头，分出来的两堆石头两两一起“粉碎”后剩余的重量值就是最小的重量值。注意，如果粉碎后的石头有剩余，那可以看作继续分成重量尽可能相近的两堆，然后继续让这两堆石头两两一起粉碎。
• 将一堆石头分成两堆重量尽可能相近的石头，设石头的重量总和为sum
  • 对于石头i，要么在第一堆里，要么在第二堆里。只针对分出来的第一堆石头，石头i要么在第一堆里，要么不在，这和 0-1 背包问题对于物品的取法是一致的。
  • 两堆石头的重量要尽可能相近，所以分出来的一堆石头的重量最大值应该是sum / 2 + sum % 2。
• 那么，问题可以转化成：“从一堆石头中任取石头，每个石头要么不取，要么取一次，得到的重量值尽可能地接近sum / 2 + sum % 2”。“物品”是石头，“背包”是一堆石头，“背包”的最大容量是sum / 2 + sum % 2，“物品”的价值是stones[i]，“物品”的重量也是stones[i]。设half为sum / 2 + sum % 2。
• dp数组及下标的含义：dp[j]表示的是，任取石头，得到的重量值不超过j的最大值，设dp[j]的更新次数为i，则dp[j]对应的可选的石头下标范围为0到i。
• 计算完dp数组后，按上述规则取石头后第一堆的重量为dp[half]，第二堆的重量为sum - dp[half]，则粉碎后剩余的重量为abs(sum - dp[half] - dp[half])。

题解代码如下

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        if (stones.empty()) return 0;
        if (stones.size() == 1) return stones.back();
        
        int sum = 0;
        for (auto& iter : stones) sum += iter;
        int half = sum / 2  + sum % 2;
        vector<int> dp(half + 1, 0);

        for (int i = 0; i < stones.size(); i++) {
            for (int j = half; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return abs(sum - dp[half] - dp[half]);
    }
};

LeetCode494 目标和

494. 目标和 - 力扣（Leetcode）

• 这道题目，从整体来看，“构造表达式”也可以看作将输入的参数分为两部分：一部分添加+号，作为被减数；另一部分添加-号，作为减数。设nums中各个整数的和为sum。设被减数为minuend（正数），减数为subtractor（正数），则两者的和为sum，两者的差为target。

• 通过以上推导，可以看出minuend的取法，即从nums中任取k个元素，使得选取的元素的和尽可能接近(sum+target)/2，当选取的元素的和恰好等于(sum+target)/2时，说明找到了一种使得构造的表达式的结果等于target的方案。

• 确定dp数组及下标的含义：dp[j]为从nums中任取整数，选取的整数的和恰好为j的情况，dp[j]的更新次数对应可以选取的nums的下标范围，设dp[j]更新了i次，dp[j]对应的可选取的nums的下标范围是0到i。

• 要注意的是，这道题目的dp数组的含义和之前的题目不同。

  • LeetCode1049 最后一块石头的重量、LeetCode416 分割等和子集，这两道题我们并不关心有多少种组合方式得到目标值，我们关心的是是否能得到目标值，或得到一个接近目标值的值。用 0-1 背包的语言来描述，就是想让背包尽可能地装满，或者装入的物品价值尽可能大。
  • 但 LeetCode494 目标和，除了要关心是否能得到目标值，还要知道有多少种方法得到目标值。用 0-1 背包的语言来描述，就是有多少种方法恰好能装满背包。此时再用描述背包装入的重量或价值的dp来解决题目就不合适了，dp数组应该描述的是有多少种方式能恰好装满容量为j的背包。

• 确定递推公式，先看简单的子问题

  • 一个元素都没有选取，选取出的minuend是空集，空集只有一种，且和为0，所以dp[0]初始化为1，此时minuend中整数的和只能是0，所以当j > 0时，dp[j]初始化为0。
  • nums[0]是第一个尝试选取的元素，如果选nums[0]，则当j == nums[0]时，dp[j]的值为1，说明得到和为nums[0]有一种方式，就是选取nums[0]。
  • 假设已经在nums[0]到nums[i-1]中选取了k个数，再选取了一个整数nums[i]。那么为了使得当前选取方式的minuend中的整数的和为j，就要再从nums[0]到nums[i-1]选出一个和为j - nums[i]的集合。根据dp数组的定义，从nums[0]到nums[i-1]选出一个和为j - nums[i]的集合的种数就是dp[j - nums[i]]。
  • 这样就可以得到递推公式，其中i为dp[j]的更新次数下标（从0开始），i=-1表示初始状态

• 初始状态已经在递推公式中写明，即dp[0]初始化为1，其他dp[j]初始化为0。

• 以nums={1, 1, 1, 1, 1}; target=3为例，根据，求得minuend=4，要注意的是，有两种情况是可以直接知道答案的种数是0的：

  1. sum的绝对值小于target的绝对值，即 abs(sum) < abs(target)，此时说明nums中的元素全取+或全取-都不可能得到值为target的和。
  2. sum + target不能被2整除，因为nums中都是整数，对于minuend的定义是从nums中取出的部分整数的和，所以minuend也应该是整数，如果sum + target不能被2整除，说明不存在minuend使得构造出的表达式的结果为target。

• 首先画出其二维dp数组，初始状态保存在i=-1那一行，对应没有从nums中选取任何整数

• 确定dp[j]的遍历顺序，即更新顺序，由递推公式 ，可以知道dp[j]的更新依赖的是上一行的且在其左边的值，所以更新顺序应该是j从大到小，即从左到右。
• 所以先滑动dp[4]，dp[4]=dp[4]+dp[4-1]=0;

• dp[2]和dp[3]同理

• 再看dp[1]，nums[0]==1，dp[1]=dp[1]+dp[1-1]=1。

• 最后看dp[0]，如果j - nums[i] > 0，则dp[0]还是1，因为没有出现空集以外的集合内元素和等于0的情况。

• 重复滑动一行的过程，把dp数组填完

• 最后的dp[minuend]就是使得构造出的表达式的结果等于target的方法数。

题解代码如下

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto& iter : nums) sum += iter;
        // 直接求得方法数为 0 的情况
        if ((sum + target) % 2) return 0;
        if (abs(sum) < abs(target)) return 0;
        // 初始化 dp 数组
        int minuend = (sum + target) / 2;
        vector<int> dp(minuend + 1, 0);
        dp[0] = 1;
        // 从 i=0 开始，逐行更新 dp 数组
        for (int i = 0; i < nums.size(); i++) {
            for (int j = minuend; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[minuend];
    }
};

LeetCode474 一和零

474. 一和零 - 力扣（Leetcode）

• 这道题目也是 0-1 背包问题，“物品”是集合中的元素，“背包”是子集。不过“物品”的“重量”变成了两个维度：一是“0”的个数，二是“1”的个数。题目要求子集中的元素个数最多，所以每个元素的“价值”是相等的，可以都设为1。

• 确定dp数组及数组下标的含义：dp[j][k]的含义是，从strs中任取字符串，这些字符串包含的 '0' 不超过 j 个，包含的 ’1‘ 不超过 k 个。对每个物品，dp[j][k]的值都会进行一次更新，所以依然可以省略遍历到第i个物品这个维度。

• 递推公式，可以看出只是“重量”多了一个维度，dp[i][j][k]还是由两种可能推出：一是不放入物品i，二是放入物品i
  

• 初始化过程隐含在dp数组的计算过程中，先将dp数组全部初始化成0。

• 同样要注意dp[j][k]的更新依赖于dp[j - numsOf0[i]][k - numsOf1[i]]，所以j应从大到小，k也应该从大到小。

题解代码如下

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> numsOf0(strs.size(), 0);
        vector<int> numsOf1(strs.size(), 0);
        for (int i = 0; i < strs.size(); i++) {
            for (auto& ch : strs[i]) {
                numsOf0[i] += ch == '0';
                numsOf1[i] += ch == '1';
            }
        }

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 0; i < strs.size(); i++) {
            for (int j = m; j >= numsOf0[i]; j--) {
                for (int k = n; k >= numsOf1[i]; k--) {
                    dp[j][k] = max(dp[j][k], dp[j - numsOf0[i]][k - numsOf1[i]] + 1);
                }
            }
        }

        return dp[m][n];
    }
};