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数组
按照我们之前的解法
dp[j] = Math.max(dp[j],dp[i- weight[i]] + value[i]) //它的意思就是 容量为 j 的背包 所容纳物品的最大价值为dp[j]
同理到这道题，我们定义dp数组的含义就可以这样定义
//容量为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组成。
实现
既然思路我们根据抽象的结果大致有了了解 ， 那么我们就可以按照动归五部曲来进行实现
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]; } }
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 的所有添加符号的方法数。】这是题目的需求
其实一开始我的思路是使用回溯算法直接将所有的结果得出，然后再返回列表大小
具体代码这里就不是实现了，具体参考代码随想录
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] 种方法
实现
根据我们的思路 就可以按照动归五部曲来进行实现
- 含义： dp[j] : 装满容量为 j 的背包 ，总共有dp[j] 种方法
- 动归表达式 ： dp[j] += dp[j - nums[i]];
- 初始化 ： dp[0] 表示装满背包容量为 0 的背包 ，总共有1种方法，那就是什么都不装
- 遍历顺序 ：外层遍历物品 ，内层遍历背包
- 打印并返回结果
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]; } }
