[Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

内容：今天复习下dp数组中的背包问题

分割等和子集 - 能否装满

最后一块石头 - 尽可能装满

目标和 - 有多少种方法装

一和零 - 装满背包有多少个物品

416. 分割等和子集

10背包：用/不用；有容量；有价值

dp[j] : 容量为j，最大价值为dp[j]

重量和价值等价

dp[target] == target 属于装满

target = sum/2

递推公式：dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

状态转移方程：只有放和不放两种情况

dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])

初始化：dp[0] = 0

其他（非零下标）=0

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int num:nums) {
            sum += num;
        }
        if(sum%2!=0) {
            return false;
        }
        int target = sum/2;
        int size = 200*100/2 + 1;
        vector<int> dp(size, 0);
        for(int i=0; i<nums.size(); ++i) {
            for(int j=target; j>=nums[i]; --j) {
                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target] == target;

    }
};

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

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int size = 30*100/2 + 1;
        vector<int> dp(size, 0);
        int sum = 0;
        for(int stone:stones) {
            sum += stone;
        }
        int target = sum/2;
        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-2*dp[target];
    }
};

494. 目标和

假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

有多少种方法装满

dp[j]：装满背包容量为j，有dp[j]种方法

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

474. 一和零

m个0，n个1的容器

装满这个背包（二维）最多几个物品

背包两个维度：dp[i][j] - i个0，j个1，最多装dp[i][j] 个物品

三个变量

递推公式：dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

重量：x个0，y个1 （用两个维度来形容物品重量）

最大容量：m个0，n个1

物品数量：dp[i-x][j-y] + 1

dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1)

dp[0][0] = 0

非零下标 = 0

先物品后重量文章来源地址https://www.toymoban.com/news/detail-571084.html

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 zeroNum =0;
            int oneNum = 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];

    }
};

到了这里，关于[Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！