494. 目标和
题目描述
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 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 +1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1 输出：1
思路分析
表达式和为target,可以看成left-right=target.即 left-(sum-left) = target=>left = (sum+target)/2
所以题目就可以转化为在集合nums中找出和为left的组合。
如何转化为0-1背包问题呢。
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = S ==> x = (S + sum) / 2
此时问题就转化为，装满容量为x背包，有几种方法。
但是此时需要注意一点:如果(S+sum) % 2 == 1,则是无解的,说明无法找到满足的.因为背包容量都是整数.
另外如果abs(target) > sum,则也无解.因为所有的数同号也无法达到target.
if(abs(target) > sum) { return 0;//没有方案 } if((sum+target) % 2==1) {//没有方案 return 0; }
动规三部曲
确定dp数组以及下标的含义
dp[j]:填满j这么大容积的背包,有dp[j]种方法
这个题也可以使用二维dp数组,dp[i] [j] = 使用下标为[0,i]的nums[i]能够凑满j这么大容积的背包需要dp[i] [j]种方法.
确定递推公式
dp[j] = dp[j] + dp[j-nums[i]] ==>dp[j] 等于不使用当前物体(数)的情况+使用当前物体(数)的情况
dp数组初始化
dp[0] = 1,装满容量为0的背包,只有一种方法,就是装0件物品.
确定遍历顺序
根据01背包问题,一维dp数组遍历,物品放在外层循环,背包容量放在内层倒序循环.
5.举例推导dp数组
nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下：
参考代码
#include<bits/stdc++.h> using namespace std; //打印dp数组 print(vector<int>& dp){ for(int i = 0;i < dp.size(); i++){ printf("%3d",dp[i]); } cout<<endl; } int findTargetSumWays(vector<int>& nums, int target) { int sum = 0; for(int i = 0; i < nums.size(); i++) { sum += nums[i]; } if(abs(target) > sum) { return 0;//没有方案 } //left - (sum - left) = target==>left = (sum+target) / 2 if((sum+target) % 2==1) {//没有方案 return 0; } int bageSize = (sum+target) / 2; vector<int> dp(bageSize+1,0); dp[0] = 1; for(int i = 0; i < nums.size(); i++) { for(int j =bageSize; j>=nums[i]; j--) { dp[j] = dp[j]+dp[j-nums[i]];//当前物体放的情况d[j-nums[i]]+当前数字不放的情况d[j]便是总情况 } //cout<<"dp["<<i<<"]"; //print(dp); } return dp[bageSize]; } int main() { vector<int> nums = {1,1,1,1,1}; int target = 3; findTargetSumWays(nums,target); return 0; }
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 。
思路分析
本题中strs 数组里的元素就是物品，每个物品都是一个！
而m 和 n相当于是一个背包，两个维度的背包。所以本题依旧是一个01背包问题
动归五部曲
确定dp数组以及下标含义
dp[i] [j]:最多有i个0和j个1的strs的最大子集大小dp[i] [j]
确定递推公式
dp[i] [j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i] [j] 就可以是 dp[i - zeroNum] [j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i] [j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。
dp数组初始化
物品价值不会是负数，初始为0，保证递推的时候dp[i] [j]不会被初始值覆盖
dp数组遍历
我们之前讲过背包一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
有同学可能想，那个遍历背包容量的两层for循环先后循序有没有什么讲究？
没讲究，都是物品重量的一个维度，先遍历那个都行！
举例推导过程
以[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3为例
最后dp数组的状态如下所示：
参考代码
#include<bits/stdc++.h> using namespace std; //打印dp void print(vector<vector<int>>& dp,int& m,int& n){ for(int i = 0;i <= m;i++){ cout<<"dp["<<i<<"]"; for(int j = 0; j<=n;j++){ cout<<dp[i][j]<<" "; } cout<<endl; } cout<<"-------------------"<<endl; } int findMaxForm(vector<string>& strs, int m, int n) {//m:0个数 n:1个数 vector<vector<int>> dp(m+1,vector<int>(n+1,0));//定义dp dp[i][j]:i个0,j个1的最大子集元素个数. print(dp,m,n); for(string str : strs){//外层遍历物体 int oneNum = 0; int zeroNum = 0; for(char ch : str) {//统计当前字符串(物体)的zero和one个数 if(ch=='0'){ zeroNum++; }else{ oneNum++; } } for(int i = m; i >= zeroNum;i--) {//遍历背包体积(二维的:字符串中m和n个数) for(int j = n; j >= oneNum;j--){ dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1); } } //print(dp,m,n); } return dp[m][n]; } int main() { vector<string> strs = {"10", "0001", "111001", "1", "0"}; int m = 5; int n = 3; findMaxForm(strs,m,n); return 0; }
518. 零钱兑换 II
题目描述
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10] 输出：1
思路分析
这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包。
但本题和纯完全背包不一样，纯完全背包是能否凑成总金额，而本题是要求凑成总金额的个数！
注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？
例如示例一：
5 = 2 + 2 + 1
5 = 2 + 1 + 2
这是一种组合，都是 2 2 1。
如果问的是排列数，那么上面就是两种排列了。
组合不强调元素之间的顺序，排列强调元素之间的顺序。
动规五步曲
确定dp数组以及下标的含义
dp[j]:凑成总金额j的货币组合数为dp[j]
确定递推公式
这个和 494.目标和相似,都是求组合,所以递推公式: dp[j] = dp[j] + dp[j - coins[i]];
dp数组如何初始化
dp[0] = 1 凑成总金额0的货币组合数为1
确定遍历顺序
本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？
前面遍历得到的是组合数,后面遍历得到的是排列数
举例推导dp数组
输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：
参考代码
#include<bits/stdc++.h> using namespace std; int change(int amount, vector<int>& coins) { vector<int> dp(amount+1,0); dp[0] = 1; for(int i = 0; i < coins.size(); i++) { for(int j = coins[i]; j <=amount; j++) { dp[j] += dp[j-coins[i]]; } } return dp[amount]; }
