动归背包2
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];
}
}