代码随想录算法训练营第四十三天|1049. 最后一块石头的重量 II，494. 目标和，474.一和零

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

题目链接：1049. 最后一块石头的重量 II

文档讲解：代码随想录

视频讲解：动态规划之背包问题，这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II

思路

将石头分成两组，两组的重量和差最小，最后相减即为最后一块石头的最小重量。

将石头重量总和整除2得到的值作为背包容量，只需要求在此背包容量下，背包所能装的最大重量。

递推公式 $dp[i] = \max{dp[j], dp[j - stones[i]] + stones[i]}$

代码

class Solution {
public:
    int lastStoneWeightII(vector<int> &stones) {
        int sum = 0;
        for (auto i : stones)
            sum += i;
        int target_sum = sum / 2;

        vector<int> dp(target_sum + 1, 0);

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

        return (sum - dp[target_sum]) - dp[target_sum];
    }
};

494. 目标和

题目链接：494. 目标和

文档讲解：代码随想录

视频讲解：动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和

思路

将数组分成相加的一组和相减的一组，分别记为 $A$ 和 $B$ ，则有等式 $A + B = s u m$ ， $A - B = t a r g e t$ ，解得 $A = (s u m + t a r g e t) /2$ ，因此转化为背包容量为 $A$ ，求装满该背包有多少种方法。

递推公式： $d p [j] + = d p [j - n u m s [i]]$

代码

class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = 0;
        for (auto i : nums)
            sum += i;

        if ((sum + target) % 2 == 1 || sum < abs(target))
            return 0;

        int bagSize = (sum + target) / 2;

        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

474.一和零

题目链接：474.一和零

文档讲解：代码随想录

视频讲解：动态规划之背包问题，装满这个背包最多用多少个物品？| LeetCode：474.一和零

思路

二维背包容量，0的最大个数和1的最大个数作为二维背包的容量，转化为01背包问题，在两个维度背包容量下，最多能装多少物品。

递推公式： $dp[i][j] = max(dp[i][j],dp[i-num_0][j-num_1] + 1)$

代码

class Solution {
public:
    int findMaxForm(vector<string> &strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (string str : strs) {
            int x = 0, y = 0;
            for (char c : str) {
                if (c == '0')
                    x++;
                else
                    y++;
            }

            for (int i = m; i >= x; i--) {
                for (int j = n; j >= y; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
                }
            }
        }

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