算法打卡 Day44（动态规划）-最后一块石头的重量 II+ 目标和 + 一和零

Leetcode 1049-最后一块石头的重量 II

题目描述

https://leetcode.cn/problems/last-stone-weight-ii/description/

解题思路

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

Leetcode 494-目标和

题目描述

https://leetcode.cn/problems/target-sum/description/

解题思路

假设 left 为正数之和，right 为负数之和的绝对值，可得：

Left + right = sum -> right = sum - left

Left - right = target -> left - (sum - left) = target

Left = (target + sum) / 2

如果右式不能整除，则证明不存在这样的表达式组合，如果可以整除，则等到正数之和，可以进一步运用 01 背包解决。

对于动规，dp[j]表示装满容量为 j 的背包的方法的个数。

01 背包先遍历物品，再遍历背包容量，因为每个物品只能使用一次

注意 01 背包的遍历顺序，物品遍历是正序，背包最大容量是倒序

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }
        int left = 0;
        if((sum + target) % 2 != 0 || sum + target < 0) return 0;
        else left = (sum + target) / 2;
        vector<int> dp(left + 1, 0);
        dp[0] = 1; //将dp[0]初始化为1
        for(int i = 0; i < n; i++){
            for(int j = left; j >= nums[i] ; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
};

Leetcode 474-一和零

题目描述

https://leetcode.cn/problems/ones-and-zeroes/description/

解题思路

dp[i][j]表示装满 i 个 0 和 j 个 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 x = 0, y = 0; //x为当前字符串0的个数，y为当前字符串1的个数
            for(char c: str){
                if(c == '0') x++;
                else if (c == '1') y++;
            }
            for(int i = m; i >= x; i--){
                for(int j = n; j >= y; j--){
                    dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1);
                }
            }
        }
        return dp[m][n];
    }
};