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

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

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

题目链接：LeetCode 1049. 最后一块石头的重量 II

思路：
sum - 2*dp[target];

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(),stones.end(), 0);
        int target = sum / 2;
        vector<int> dp(target+1);
        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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意 ：

1. 注意从0开始

LeetCode 494. 目标和

题目链接：LeetCode 494. 目标和

思路：
组合问题，就是将所有没放nums[i]的情况 加上现有情况，遍历。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if((sum+target)%2) return 0;
        if(abs(target)>sum) return 0;
        int space = (sum+target)/2;
        vector<int> dp(space+1,0);
        dp[0] = 1;
        for(int i=0; i<nums.size(); i++){
            for(int j=space; j>=nums[i]; j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[space];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

注意 ：

1. 注意从0开始

LeetCode 474.一和零

题目链接：LeetCode 474.一和零

思路：

1

注意 ：
1.
2.
3.
4.

LeetCode 704 二分查找

题目链接：LeetCode 704 二分查找

思路：

二维01背包

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        dp[0][0] = 0;

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

注意 ：

1. 好好体会