代码随想录算法训练营第42天 [1049. 最后一块石头的重量 II 494. 目标和 474.一和零]

代码随想录算法训练营第42天 [1049. 最后一块石头的重量 II 494. 目标和 474.一和零]

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

链接: 代码随想录.
思路：石头相撞重量最小，最小的情况就是刚好分为两组大小相同的，这样相撞后重量就为0
所以转化为 重量之和的一半 target容量的背包，尽可能装满，石头的重量和价值都是stones[i]
dp[j] 容量为j的背包最大重量为dp[j]
做题状态：看解析后做出来了

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        //石头相撞重量最小，最小的情况就是刚好分为两组大小相同的，这样重量就为0
        //所以转化为 重量之和的一半 target容量的背包，尽可能装满，石头的重量和价值都是stones[i]
        //dp[j] 容量为j的背包最大重量为dp[j]
        int sum = 0;
        for(int n : stones){
            sum+=n;
        }
        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. 目标和

链接: 代码随想录.
思路：

将数组中需要添加+的记为left ,需要添加-的记为right
数组元素中的和为sum，数组元素加了符号后的和为targeet
得到 left+right = sum left-right = target
推导得到 left = (sum+target)/2 如果不能整除，肯定没有解，直接返回0
代入一下示例 left = (5+3)/2 = 4
相当于left的和要凑为4
相当于背包容量为4，从nums中取物品装满背包有多少种方式
dp[j] 表示容量为j的背包，有dp[4]种方式
dp[0] = 1
递推公式 dp[j] += dp[j-nums[i]]

做题状态：看解析后做出来了

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 将数组中需要添加+的记为left ,需要添加-的记为right
        // 数组元素中的和为sum，数组元素加了符号后的和为targeet
        // 得到 left+right = sum  left-right = target
        // 推导得到  left = (sum+target)/2  如果不能整除，肯定没有解，直接返回0
        // 代入一下示例  left = (5+3)/2 = 4
        // 相当于left的和要凑为4
        // 相当于背包容量为4，从nums中取物品装满背包有多少种方式
        // dp[j] 表示容量为j的背包，有dp[4]种方式
        // dp[0] = 1
        //  递推公式  dp[j] += dp[j-nums[i]]
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if ((sum + target) % 2 == 1 || abs(target) > sum) {
            return 0;
        }
        int temp = (sum + target) / 2;
        vector<int> dp(temp + 1);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = temp; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[temp];
    }
};

三、474.一和零

链接: 代码随想录.
思路：一共有str种物品，要同时满足m个0的背包和n个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 one = 0;
            int zero = 0;
            for (char s : str) {
                if (s == '1') {
                    one++;
                } else {
                    zero++;
                }
            }

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

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