目录

一、(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];
    }
};
11-06 14:20