474. 一和零

力扣题目链接

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

  • 输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
  • 输出：4
  • 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。 其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

  • 输入：strs = [“10”, “0”, “1”], m = 1, n = 1
  • 输出：2
  • 解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 ‘0’ 和 ‘1’ 组成
  • 1 <= m, n <= 100

题目分析

初次接触这种题 ，我基本上是想不出很好的解法，但是学了dp之后 ，才开始学会慢慢的将题目抽象化。但是对于这道题，我还是很难相处如何抽象成为我们能够接触的算法

跟随代码随想录的脚步 ，我才清楚的知道如何 解决这类题，如何抽象题目的信息作为我们解题的关键

思路

从题目中【请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 】这是我们需要得到的结果。那么我们就可以以这个为着手点。

其包括两个变量 m 个 0 和 n 个 1。那么按照一维数组的思路是很难说清楚的。所以我们这里用二维数组来定义dp数组

按照我们之前的解法

1
2
dp[j] =  Math.max(dp[j],dp[i- weight[i]] + value[i])
//它的意思就是 容量为 j 的背包 所容纳物品的最大价值为dp[j]

同理到这道题，我们定义dp数组的含义就可以这样定义

1
2
//容量为i个0和 j个1组成的背包  所能容纳的物品的最大数量(子集个数)为dp[i][j]
dp[i][j] = Math.max(dp[i][j],dp[i- zeroNumber][j - oneNumber] + 1); //加1代表的是自己个数+1

**那么我们抽象的结果就是： **

物品(子集) 是由 0和1组成。

背包（子集个数）是由 m个0 和 n个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
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //每个物品"10" ,"0001"...表示的是一个由 x个0 和 y个1组成
        //1. 首先确定dp数组的含义
        //2. 确 定递推公式
        //dp[i][j] 是指有i 个 0 和 j 个 1 组成的容器所能存储的物品的最大数量为dp[i][j]
        int[][] dp = new int[m+ 1][n +1];
        //3. 初始化dp数组     
        //dp[0][0] = 0 就是代表由0个0 和 0个1组成的容器能够存储的物品最大数量为0
        dp[0][0]=0;
        //4. 确定遍历顺序
        for(int i = 0 ;i <strs.length;i++){
            //先得出每个商品的 0 和 1 的个数
            int zeroNumber = 0;
            int oneNumber = 0;
            for(int k = 0;k < strs[i].length();k++){
                if(strs[i].charAt(k) == '0'){
                    zeroNumber++;
                }else{
                    oneNumber++;
                }
            }
            //然后遍历内层背包
            for(int x = m; x >= zeroNumber;x--){
                for(int y = n; y >= oneNumber; y--){
                    dp[x][y] = Math.max(dp[x][y],dp[x - zeroNumber][y - oneNumber] + 1);
                }
            }
        }
        //5.打印dp数组及返回结果
        return dp[m][n];
    }
}

image-20230322150215008

494. 目标和

力扣题目链接

难度：中等

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

  • 输入：nums: [1, 1, 1, 1, 1], S: 3
  • 输出：5

解释：

  • -1+1+1+1+1 = 3
  • +1-1+1+1+1 = 3
  • +1+1-1+1+1 = 3
  • +1+1+1-1+1 = 3
  • +1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

提示：

  • 数组非空，且长度不会超过 20 。
  • 初始的数组的和不会超过 1000 。
  • 保证返回的最终结果能被 32 位整数存下。

题目分析

还是按照之前的分析方法【返回可以使最终数组和为目标数 S 的所有添加符号的方法数。】这是题目的需求

其实一开始我的思路是使用回溯算法直接将所有的结果得出，然后再返回列表大小

具体代码这里就不是实现了，具体参考代码随想录

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();
    }
};

最后运行的结果显示超时了。所以说回溯的解法是靠不住的。这里我们就可以用到动态规划了

思路

首先得到我们数组的总和为sum ，那么目标结论就是target = 加法总和 - 减法总和

假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为，装满容量为加法总和（x）的背包，有几种方法。

那么dp数组的含义我们就可以确定下来了

dp[j] : 装满容量为 j 的背包 ，总共有dp[j] 种方法

实现

根据我们的思路 就可以按照动归五部曲来进行实现

  1. 含义： dp[j] : 装满容量为 j 的背包 ，总共有dp[j] 种方法

  2. 动归表达式 ： dp[j] += dp[j - nums[i]];

  3. 初始化 ： dp[0] 表示装满背包容量为 0 的背包 ，总共有1种方法，那就是什么都不装

  4. 遍历顺序 ：外层遍历物品 ，内层遍历背包

  5. 打印并返回结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
		//如果target过大 sum将无法满足
        if ( target < 0 && sum < -target) return 0;
        if ((target + sum) % 2 != 0) return 0;
        int size = (target + sum) / 2;
        if(size < 0) size = -size;
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }
}