【代码随想录第45天】动态规划5

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

LeetCode题目：1049. 最后一块石头的重量 II
代码随想录：1049. 最后一块石头的重量 II

思路就是尽量把石头分成重量总和相等的两堆，想明白这个，就跟416题没什么区别了

class Solution {
public:
//尽量把石头分成重量总和相等的两堆
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int n : stones){
            sum += n;
        }
        int target = sum / 2;
        vector<int> dp(target + 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 abs(dp[target] - (sum-dp[target]));

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

494. 目标和

LeetCode题目： 494. 目标和
代码随想录： 494. 目标和

假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2,此时问题就转化为，装满容量为x的背包，有几种方法。
若不能整除2，无解，直接return 0
01背包问题
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
递推公式：dp[j] += dp[j - nums[i]]
初始化dp[0] = 1

   int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
        }
        if (abs(target) > sum) return 0;
        if((target + sum) % 2 == 1) return 0;
        int x = (target + sum) / 2;
        vector<int> dp(x + 1); //装满容量为x的背包有多少种方法
        dp[0] = 1;
        for(int i = 0; i < nums.size(); i++){
            for(int j = x; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[x];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：O(n × m)，n为正数个数，m为背包容量
空间复杂度：O(m)，m为背包容量

474.一和零

LeetCode题目：474.一和零
代码随想录：474.一和零

m 和 n相当于是一个背包，两个维度的01背包。
二维dp[i][j]：装满i个0，j个1最多背了dp[i][j]个物品.

01背包：dp[j] = max(dp[j], dp[j - weight] + val[i])
每个物品重量为: x 个 0， y 个1
则有：
dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
初始化：0

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;
            for(char c : str){
                if(c == '0') x++;
                else 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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20