代码随想录 | Day38 | 动态规划 ：01背包应用 目标和&&一和零

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

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

难点：

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

494.目标和（恰好等于背包容量求方案数）

494. 目标和 - 力扣（LeetCode）

思路分析：

设前面要加“+”的数和为p，前面要加“-”的数的和为q。

p+q=sum（数组所有元素的和）

p-q=target（要加正号的减去要加负号的）

2p=sum+target

p=(sum+target)/2

也就是说呢，我们要在nums数组里面找一个子集，让子集的和等于p，能找到几个就有几种方案

1.回溯法

本题也可以使用回溯暴力枚举，直接搜索nums里面的所有组合，等于target的就是答案。

这是组合总和的代码，当然是超时的

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
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (S > sum) return 0; // 此时没有方案
        if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要格外小心数值溢出的问题
        int bagSize = (S + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和

        // 以下为回溯法代码
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 需要排序
        backtracking(nums, bagSize, 0, 0);
        return result.size();
    }
};

2.01背包

如何转换为01背包呢？

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

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

3.而我们背包的容量c就是target这个值，只要我们的方案可以刚好把背包给填满了，那说明背包里面放进去的nums[i]加和就是target

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

转变为01背包后的递推公式变化？

dp/dfs表示从前 i 个数中从选一些数恰好组成 j 的方案数

就是从前i个数里面随便选，能正号填满容量j的方案数

只需要把01背包的max换成+即可

1
dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]];

dp[i][j]是由两个情况相加得到的。我们没有选第i件物品和选了第i件物品

选了那方案数就得加上在容量为j-w[i]的情况下的方案数

没选那方案数就得加上选上一个物品的时候在容量为j的情况下的方案数（上一个物品也分为选或不选）

这里是加法原理，选和不选第i个物品的情况是互斥的，我们要得到所有的方案数量就需要把它加起来

1.回溯暴力枚举

1.参数和返回值

i是物品编号

c是当前容量

nums是题数组

dfs(i,c) 表示从前 i 个数中从选一些数恰好组成 c 的方案数

1
int dfs(int i,int c,vector<int>& nums)

2.终止条件

1.i<0说明没有物品可以选了，如果当前容量正好等于0，那就返回1说明找到了一个合法方案

不等于0就返回0说明没找到

2.如果当前容量已经小于了物品所需的容量，那说明背包装不下，那就只能不选这个物品了，就返回不选这个物品的方案数量，即在前i-1个物品里面能凑够容量c的方案数

1
2
3
4
5
6
7
if(i<0)
          if(c==0)
              return 1;
          else
              return 0;
      if(c<nums[i])
          return dfs(i-1,c,nums);

3.本层逻辑

返回 在前i个物品中，选了第i个物品能满足c的方案数和没选第i个物品能满足c的方案数之和

1
return dfs(i-1,c-nums[i],nums)+dfs(i-1,c,nums);

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int dfs(int i,int c,vector<int>& nums)
    {
        if(i<0)
            if(c==0)
                return 1;
            else
                return 0;
        if(c<nums[i])
            return dfs(i-1,c,nums);
        return dfs(i-1,c-nums[i],nums)+dfs(i-1,c,nums);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int c:nums)
            sum+=c;
        int p=sum+target;
        if (p < 0 || p % 2 != 0)
            return 0;
        target=p/2;
        return dfs(nums.size()-1,target,nums);
    }
};

2.记忆化搜索

还是老样子

初始化dp为-1，如果不是-1说明计算过了直接返回

并且在返回之前给dp赋值

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
class Solution {
public:
    int dfs(int i,int c,vector<int>& nums,vector<vector<int>>& dp)
    {
        if(i<0)
            if(c==0)
                return 1;
            else
                return 0;
        if(c<nums[i])
            return dp[i][c]=dfs(i-1,c,nums,dp);
        if(dp[i][c]!=-1)
            return dp[i][c];
        return dp[i][c]=dfs(i-1,c-nums[i],nums,dp)+dfs(i-1,c,nums,dp);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int c:nums)
            sum+=c;
        int p=sum+target;
        if (p < 0 || p % 2 != 0)
            return 0;
        target=p/2;
        vector<vector<int>> dp(nums.size(),vector<int>(target+1,-1));
        return dfs(nums.size()-1,target,nums,dp);
    }
};
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
//lambda
class Solution {
public:

    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int c:nums)
            sum+=c;
        int p=sum+target;
        if (p < 0 || p % 2 != 0)
            return 0;
        target=p/2;
        vector<vector<int>> dp(nums.size(),vector<int>(target+1,-1));
        function<int(int,int)> dfs=[&](int i,int c)->int{
            if(i<0)
                if(c==0)
                    return 1;
                else
                    return 0;
            if(c<nums[i])
                return dp[i][c]=dfs(i-1,c);
            if(dp[i][c]!=-1)
                return dp[i][c];
            return dp[i][c]=dfs(i-1,c-nums[i])+dfs(i-1,c);
        };
        return dfs(nums.size()-1,target);
    }
};

3.1:1翻译为动态规划

注意这里把dp数组里面的下标i都加了1（重点）

因为这样做可以避免负数下标的出现

一种好理解的方式是dp[i][j]含义是在前i个物品里面选，容量刚好满足j

物品编号是1-i，而不是0-i

那为什么nums数组的下标没有加+1呢？

因为nums数组从0开始的，dp数组中的i，表示第i件物品，而第i件物品的重量和价值和nums[i-1]

1
dp[i+1][j]=dp[i][j]+dp[i+1][j-nums[i]];

关于初始化就看上面回溯的终止条件

i<0&&c==0就为1，那里的i是我们这里的i-1，因为我们给dp数组的i下标都加了1

也就是说

dp[i][0]全都为1

但这里只需要把dp[0][0]=1就行，其他的会在循环中给他赋值的，最后打印出来也确实是1

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int c:nums)
            sum+=c;
        int p=sum+target;
        if (p < 0 || p % 2 != 0)
            return 0;
        target=p/2;
        vector<vector<int>> dp(nums.size()+1,vector<int>(target+1,0));
        dp[0][0]=1;
        for(int i=0;i<nums.size();i++)
            for(int j=0;j<=target;j++)
                if(j<nums[i])
                    dp[i+1][j]=dp[i][j];
                else
                    dp[i+1][j]=dp[i][j]+dp[i][j-nums[i]];
        return dp[nums.size()][target];
    }
};

4.滚动数组优化

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

474.一和零

474. 一和零 - 力扣（LeetCode）

思路分析：

这道题我也没想到怎么联系到01背包，或者说怎么应用

看了题解以后才了解到了

咱们平时的容量限制是物品i的重量

今天的容量限制是物品i（字符串strs[i]）里面的0和1的数量，就是说有两个限制，一个是0的数量，一个是1的数量，说明这是一个三维数组，而每个物品i（字符串strs[i]）的价值是多少？

因为求的是子集的数量，所以每一个字符串的价值都为1，就是放这个字符串i进去，就加1，不放就不加

举例：

比如说我们放的放的，背包容量只能装2个0和三个1了

那我们下一个strs[i]如果是 000111，有3个0，3个1那也放不进去

001111也不行

0000也不行

就是两个要都满足

比如0011，然后放进去以后最大的方案数+1

所以本质上就是01背包的容量多加了一个维度

递推公式直接仿照着写

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
1
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - zeronum][k - onenum] + 1);

当前的最大数量那就是不放当前字符串和放了当前字符串这两种情况里面选一个最大值，如果我我们选了当前字符串那就+1，因为dp含义是在前i个字符串里面选的最多有j个0和k个1的子集中的字符串数量。

1.回溯暴力枚举

1.参数和返回值

i是物品编号，标识到了第几个字符串了

j是当前0的容量，k是当前1的容量

strs是题数组

dfs(i,j,k,strs) 含义是在前i个字符串里面选的最多有j个0和k个1的子集中的字符串数量

1
int dfs(int i,int j,int k,vector<string>& strs)

2.终止条件

1.i<0说明没有物品可以选了，如果当前容量正好等于0，那就返回1说明找到了一个合法方案

不等于0就返回0说明没找到

2.如果当前容量已经小于了物品所需的容量，那说明背包装不下，那就只能不选这个物品了，就返回不选这个物品的方案数量，即在前i-1个物品里面能凑够容量c的方案数

1
2
3
4
if(i<0)
	return 0;
if(j<zeronum || k<onenum)//0和1只要有一个不够就不放 
	return dfs(i-1,j,k,strs);

3.本层逻辑

返回当前的最大数量，就是不放当前字符串和放了当前字符串这两种情况里面选一个最大值

1
2
3
4
5
6
7
8
9
10
int zeronum=0;
      int onenum=0;
      for(auto c:strs[i])
          if(c=='0')
              zeronum++;
          else
              onenum++;
      if(j<zeronum || k<onenum)
          return dfs(i-1,j,k,strs);
      return max(dfs(i-1,j,k,strs),dfs(i-1,j-zeronum,k-onenum,strs)+1);

完整代码

当然是超时的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int dfs(int i,int c,vector<int>& nums)
    {
        if(i<0)
            if(c==0)
                return 1;
            else
                return 0;
        if(c<nums[i])
            return dfs(i-1,c,nums);
        return dfs(i-1,c-nums[i],nums)+dfs(i-1,c,nums);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int c:nums)
            sum+=c;
        int p=sum+target;
        if (p < 0 || p % 2 != 0)
            return 0;
        target=p/2;
        return dfs(nums.size()-1,target,nums);
    }
};

2.记忆化搜索

还是老样子

初始化dp为-1，如果不是-1说明计算过了直接返回

并且在返回之前给dp赋值

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
class Solution {
public:
    int dfs(int i,int j,int k,vector<string>& strs,vector<vector<vector<int>>>& dp)
    {
        if(i<0)
            return 0;
        int zeronum=0;
        int onenum=0;
        for(auto c:strs[i])
            if(c=='0')
                zeronum++;
            else
                onenum++;
        if(dp[i][j][k]!=-1)
            return dp[i][j][k];
        if(j<zeronum || k<onenum)
            return dp[i][j][k]=dfs(i-1,j,k,strs,dp);
        
        return dp[i][j][k]=max(dfs(i-1,j,k,strs,dp),dfs(i-1,j-zeronum,k-onenum,strs,dp)+1);
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<vector<int>>> dp(strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,-1)));
        return dfs(strs.size()-1,m,n,strs,dp);
    }
};
1
2
//lambda
虚晃一枪，笔者懒得写了，大家自己写吧

3. 1:1翻译为动态规划

多加了初始化部分，就是物品1，能放下的地方初始化为1，放不下的初始化为0

1
2
3
4
5
6
7
8
9
10
11
12
13
int zeronum=0;
      int onenum=0;
      for(auto c:strs[0])
          if(c=='0')
              zeronum++;
          else
              onenum++;
      for(int j=0;j<=m;j++)
          for(int k=0;k<=n;k++)
              if(j<zeronum||k<onenum)
                  dp[0][j][k]=0;
              else
                  dp[0][j][k]=1;

完整代码：

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
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<vector<int>>> dp(strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,0)));
        int zeronum=0;
        int onenum=0;
        for(auto c:strs[0])
            if(c=='0')
                zeronum++;
            else
                onenum++;
        for(int j=0;j<=m;j++)
            for(int k=0;k<=n;k++)
                if(j<zeronum||k<onenum)
                    dp[0][j][k]=0;
                else
                    dp[0][j][k]=1;
        for(int i=1;i<strs.size();i++)
        {
            zeronum=0;
            onenum=0;
            for(auto c:strs[i])
                if(c=='0')
                    zeronum++;
                else
                    onenum++;
            for(int j=0;j<=m;j++)
                for(int k=0;k<=n;k++)
                    if(j<zeronum||k<onenum)
                        dp[i][j][k]=dp[i-1][j][k];
                    else
                        dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeronum][k-onenum]+1);
        }
        return dp[strs.size()-1][m][n];
    }
};

4.滚动数组优化

和01背包一样，先遍历物品

容量倒着遍历

删掉物品编号那一维

除了初始化为0不需要其他的初始化动作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=0;i<strs.size();i++)
        {
            int zeronum=0;
            int onenum=0;
            for(auto c:strs[i])
                if(c=='0')
                    zeronum++;
                else
                    onenum++;
            for(int j=m;j>=zeronum;j--)
                for(int k=n;k>=onenum;k--)
                        dp[j][k]=max(dp[j][k],dp[j-zeronum][k-onenum]+1);
        }
        return dp[m][n];
    }
};