代码随想录 | Day37 | 动态规划 ：01背包应用 分割等和子集 && 最后一块石头的重量II

动态规划应该如何学习？-CSDN博客

01背包模板 | 学习总结-CSDN博客

难点：

代码都不难写，如何想到01背包并把具体问题抽象为01背包才是关键

416.分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

思路分析：

主要说一下如何转换成可以应用01背包的情景

其实就是想办法把nums数组分成两半，然后看能不能让这两半的和相等就完事

那肯定要先加起来得到sum然后取余二咯，不等于0直接滚蛋

等于的话那就sum除以2，然后在nums数组里面找一个组合，让他的和等于sum/2

听起来是不是像组合总和，emm没错包一样的，想要这么做的小伙伴也可以尝试一下

如何转换为01背包呢？

1.因为是子集，所以每个数只有选或者不选两个选项，不会有重复

2.就是把nums里面的数字当做物品，他们的价值和重量全是他们本身的数值

3.而我们背包的容量c就是sum/2这个值，只要我们得到的最大价值刚好把背包给填满了，那说明背包里面这几个数加起来就是容量（因为价值=重量=自身数值），我们就找到了这个子集，就可以返回true了

如果不是刚好填满，那肯定找不出子集加起来正好是sum

然后在这里找一个模板套就完事了

01背包模板 | 学习总结-CSDN博客

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto c:nums)
            sum+=c;
        if(sum%2!=0)
            return false;
        sum/=2;
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<int> dp(sum+1,0);
        for(int i=0;i<nums.size();i++)
            for(int j=sum;j>=w[i];j--)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        if(dp[sum]==sum)
            return true;
        return false;
    }
};

笔者在写01背包模板的时候用这道题做的测试，下面简单记录一下不想看的跳过就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    /*int dfs(vector<int>& w,vector<int>& v,int i,int c,vector<vector<int>>& dp)
    {
        if(i<0)
            return 0;
        if(dp[i][c]!=-1)
            return dp[i][c];
        if(c<w[i])
            return dp[i][c]=dfs(w,v,i-1,c,dp);
        return dp[i][c]=max(dfs(w,v,i-1,c,dp),dfs(w,v,i-1,c-w[i],dp)+v[i]);
    }*/
    /*function<int(int,int)> dfs=[&](int i,int c)->int{
            if(i<0)
            return 0;
            if(dp[i][c]!=-1)
                return dp[i][c];
            if(c<w[i])
                return dp[i][c]=dfs(i-1,c);
            return dp[i][c]=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]);
        };*/
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto c:nums)
            sum+=c;
        if(sum%2!=0)
            return false;
        sum/=2;
        vector<int> w(nums.begin(),nums.end());
        vector<int> v(nums.begin(),nums.end());
        vector<int> dp(sum+1,0);
        for(int i=0;i<nums.size();i++)
            for(int j=sum;j>=w[i];j--)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        /*vector<vector<int>> dp(nums.size(),vector<int>(sum+1,0));
        for(int i=w[0];i<=sum;i++)
            dp[0][i]=v[0];
        for(int i=1;i<nums.size();i++)
            for(int j=0;j<=sum;j++)
                if(j>=w[i])
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                else
                    dp[i][j]=dp[i-1][j];*/
        if(dp[sum]==sum)
            return true;
        return false;
    }
};

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

1049. 最后一块石头的重量 II - 力扣（LeetCode）

思路分析：

其实就是尽量把石头分成两堆，然后让这两堆的重量相差最小，这样碰完就剩下的最小

所以就和上面那道题差不多

也是把数组累加，然后把sum/2当做容量

得出以sum/2作为容量的时候，我们可以搜集到的最大重量和。

注意最后返回是sum减去两次dp[c]，减去两次是因为sum/2会向下取整

sum-dp[c]一定是大于等于dp[c]的，而在题目中的意思，这个代表了还可以继续粉碎。

比如加和sum为23的话，dp[c]最大就是11，23-11-11=1就是最小了

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(auto c:stones)
            sum+=c;
        int c=sum/2;
        vector<int> dp(c+1,0);
        for(int i=0;i<stones.size();i++)
            for(int j=c;j>=stones[i];j--)
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
        return sum-dp[c]-dp[c];
    }
};