代码随想录算法训练营第23期day42|1049. 最后一块石头的重量II、494. 目标和、474.一和零

目录

一、（leetcode 1049）最后一块石头的重量II

二、（leetcode 494）目标和

三、（leetcode 474）一和零

---

一、（leetcode 1049）最后一块石头的重量II

力扣题目链接

将石头重量分成两堆，这两堆的重量要尽可能相近。计算其中一堆的最大重量，因为sum/2向下取整，所以dp[target]肯定是重量较轻的那一堆，最后的答案就是重量较大的那一堆减去dp得到的这一堆，也就是(sum-dp[target]) - dp[target]。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0, len = stones.size();
        for(int i = 0; i < len; ++i){
            sum += stones[i];
        }
        int target = sum / 2;
        vector<int> dp(15001, 0);
        for(int i = 0; i < len; ++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];
    }
};

二、（leetcode 494）目标和

力扣题目链接

原题的回溯方法比较符合直觉，很难在没有做过的情况下和01背包或者说分割等和子集的方法联系起来。要多好好想想

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0, len = nums.size();
        for(int i = 0; i < len; ++i) { sum += nums[i]; }
        if(abs(target) > sum) return 0;
        if((target+sum) % 2 == 1) return 0;
        int bagsize = target + sum >> 1;
        vector<int> dp(bagsize+1, 0);
        dp[0] = 1;
        for(int i = 0; i < len; ++i){
            for(int j = bagsize; j >= nums[i]; --j){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[bagsize];
    }
};

三、（leetcode 474）一和零

力扣题目链接

不要因为有m和n的限制就觉得这是多重背包，这里的m和n只是不同维度上的限制，题目本质上还是01背包（但是怎么关联上还是有困难啊）。

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 oneNum = 0, zeroNum = 0;
            for(char 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];
    }
};