「代码随想录算法训练营」第三十一天 | 动态规划 part4

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

题目链接:https://leetcode.cn/problems/last-stone-weight-ii/
题目难度:中等
文章讲解:https://programmercarl.com/1049.最后一块石头的重量II.html
视频讲解:https://www.bilibili.com/video/BV14M411C7oV/
题目状态:看题解过

思路:

本题本质上就是将石头分为两堆进行撞击,判断剩余最小的重量是多少。这样理解的话就将题转换为了416. 分割等和子集问题了。
首先定义 dp 数组的含义,dp[j] 表示选择重量为 j 的情况下,这堆石头的剩余重量。
而 dp[j] 的值可以由 max(dp[j], dp[j - stones[i]] + stones[i]) 来表示,其中 dp[j - stones[i]] 是保留一定的重量可以将当前遍历到的石头放进去(可以联想为放入一个容器里),而加上 stones[i] 的含义就是将当前遍历到的石头重量加进去。

代码:

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(auto &stone : stones) sum += stone;
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        for(int i = 0; i < stones.size(); ++i) {
            for(int j = target; j >= stones[i]; --j) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};

494. 目标和

题目链接:https://leetcode.cn/problems/target-sum/
题目难度:中等
文章讲解:https://programmercarl.com/0494.目标和.html
视频讲解:https://www.bilibili.com/video/BV1o8411j73x/
题目状态:这题转换思维真绕,看别人评论学习学习,思路来自B站用户@皮特皮特Peter在本题视频讲解下的留言。

思路:

将 nums 中元素分为左右两个部分,一部分是正集合 left,另一部分是负集合 right。
举例看一下:[1,1,1,1,1]
由题意可知:

  1. 正数集合 left - 负数集合 right = 目标值 traget。比如:[1,1,1,1] - [1] = 3
  2. 正数集合 left + 负数集合 right = 数组总和 sum。比如: [1,1,1,1] + [1] = 5

我们只要得知凑出 left 正集合有多少种组合方式 就等同于题目问题:凑成目标和有多少种方式。
于是相当于说每个元素放不放进正数的集合里 等同于背包问题中的拿或不拿。
所以我们要的结果是:数组中能够凑成背包容量为正集合 left 的最大组合方案数
而left可以用可知的 1 和 2 代入解出为 left = (sum + target) / 2
然而 left 代表的是正数集要多少个才能凑成目标和 target(正数集个数确定负数集也就确认) 除以 2 存在不能整除情况
所以不能整除说明凑不成目标和 所以没有方法可以凑成目标和,返回 0。

dp 数组的含义: 表示要凑成容量为 j 的背包有多少种方案。

初始化:其他非 0 容量的背包 使用一维数组的递推公式从右向左覆盖数组推导演算。任何一个物品 只要选择不取这种方案 都能凑成0容量的背包。

递推公式: dp[j] = 不放入nums[i]的最大组合方案 + 放入nums[i]的最大组合方案(即取不取进正数集里面)

  • 对应一维:dp[j] = dp[j] + dp[j - nums[i]]
  • 对应二维:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]

代码:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto &num : nums) sum += num;
        if(abs(target) > sum) return 0;
        if((target + sum ) % 2 == 1) return 0;
        int bagSize = (target + sum) / 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];
    }
};

回溯法代码:

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtarcking(vector<int> &candidates, int target, int sum, int startIdx) {
        if(sum == target) res.push_back(path);

        for(int i = startIdx; i < candidates.size() && sum + candidates[i] <= target; ++i) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtarcking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();
        }
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto &num : nums) sum += num;
        if(target > sum) return 0;
        if((target + sum) % 2) return 0;
        int bagSize = (target + sum) / 2;

        res.clear();
        path.clear();
        sort(nums.begin(), nums.end());
        backtarcking(nums, bagSize, 0, 0);
        return res.size();
    }
};

474. 一和零

题目链接:https://leetcode.cn/problems/ones-and-zeroes/
题目难度:中等
文章讲解:https://programmercarl.com/0474.一和零.html
视频讲解:https://www.bilibili.com/video/BV1rW4y1x7ZQ/
题目状态:不会,看题解

思路:

看完题解之后感觉还是那种背包问题,只不过这次的动规数组是个二维数组,用来存储 0 和 1 的数量,比较绕的就是还要计算一下二进制字符串中所含的 0 和 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(auto &str : strs) {
            int oneNum = 0, zeroNum = 0;
            for(auto &c : str) {
                if(c == '0') zeroNum++;
                else oneNum++;
            }
            for(int i = m; i >= zeroNum; --i) {
                for(int j = n; j >= oneNum; --j) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

热门相关:新婚夜,大佬调戏娇妻上瘾了   逆流纯真年代   腹黑老公,请离婚!   我能改变东西颜色   末日之最终战争