代码随想录day43:动态规划part05：01背包

1049.最后一块石头的重量

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int i=0;i<stones.size();i++){
            sum+=stones[i];
        }
        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]);
                //cout<
            }
        }
        return sum-dp[target]-dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

494.目标和

• 递推公式的思路–凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包
1
2
3
4
5

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

• 特殊情况的判断：abs(target)>sum。即：即使所有的nums[i]前都是加号或者都是减号也无法满足需求。

class Solution
public:
    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((sum+target)%2) return 0;
        int bagweight=(sum+target)/2;
        vector<int> dp(bagweight+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++){
            for(int j=bagweight;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
                //cout<
            }
        }
        return dp[bagweight]; 

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

474.一和零

0，1背包问题，一维数组里边背包容量的遍历一定是倒序，否则会不断同时加入同一个字符串。
mn看起来是两维，其实都是容量问题。

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 zero=0;int one=0;
            for(char c:str){
                if(c=='0') zero++;
                if(c=='1') one++;
            }
            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);
                    //cout<
                }
            }
        }
        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