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
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
思路
本题其实可以用回溯法实现,每个元素都有+-两种状态,但是整个时间复杂度会达到2n次方,所以我们改用动态规划法。
与之前的最后一块石头的重量Ⅱ类似,这道题也可以把数分为两部分,一部分前添加+,一部分前添加-,分别记为left和right,left+right=sum,left-right=target,那么left=(sum+target)/2
所以在left已知的情况下,我们只需要得出nums中所有相加能得到left的组合数即可。此处需要注意如果sum+target是奇数,那么left无法得出,直接返回0.
定义一个二维dp数组new int[n+1][left+1],dp[i][j]表示数组前i位能够组成目标j的组合数。递推公式为:
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]](j>=nums[i-1])或 dp[i][j]=dp[i-1][j];
最后dp[n][left]即为最终的答案。
代码
class Solution {
public int findTargetSumWays(int[] nums, int target) {int sum=0;int n=nums.length;for(int i:nums){sum+=i;}if((sum+target)%2==1||(sum+target<0)){return 0;}int left=(sum+target)/2;int[][] dp=new int[n+1][left+1];dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=left;j++){if(j>=nums[i-1]){dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];}else {dp[i][j]=dp[i-1][j];}}}return dp[n][left];}
}
还可以使用滚动数组的方式优化空间复杂度
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}int diff = sum - target;if (diff < 0 || diff % 2 != 0) {return 0;}int neg = diff / 2;int[] dp = new int[neg + 1];dp[0] = 1;for (int num : nums) {for (int j = neg; j >= num; j--) {dp[j] += dp[j - num];}}return dp[neg];}
}
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
思路
这道题虽然也是01背包的传统思路,但是有个很大的不同是背包容量有两个元素m和n,但是其实只要在dp数组增加一个维度即可。
另外,本题要找的是子集的最大长度,和组合数又有一些区别,遍历到一个dp[i][j][k]时,若j>=str[i]中的0个数且k>=1个数时,将其更新为它与dp[i-1][j-zero][k-one]中的较大值
代码
class Solution {
public int findMaxForm(String[] strs, int m, int n) {int length=strs.length;int[][][] dp=new int[length+1][m+1][n+1];for(int i=1;i<=length;i++){int one=0,zero=0;for(int j=0;j<strs[i-1].length();j++){if(strs[i-1].charAt(j)=='0'){zero++;}else {one++;}}for(int k=0;k<=m;k++){for(int l=0;l<=n;l++){dp[i][k][l]=dp[i-1][k][l];if(k>=zero&&l>=one){dp[i][k][l]=Math.max(dp[i][k][l],dp[i-1][k-zero][l-one]+1);}}}}return dp[length][m][n];}
}
滚动数组法
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m + 1][n + 1];int length = strs.length;for (int i = 0; i < length; i++) {int[] zerosOnes = getZerosOnes(strs[i]);int zeros = zerosOnes[0], ones = zerosOnes[1];for (int j = m; j >= zeros; j--) {for (int k = n; k >= ones; k--) {dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);}}}return dp[m][n];}public int[] getZerosOnes(String str) {int[] zerosOnes = new int[2];int length = str.length();for (int i = 0; i < length; i++) {zerosOnes[str.charAt(i) - '0']++;}return zerosOnes;}
}
518.零钱兑换Ⅱ
给你一个整数数组 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
提示:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins
中的所有值 互不相同0 <= amount <= 5000
思路
这题属于完全背包问题,完全背包和01背包的区别在于完全背包中所有物体都有无限个,它与01背包思路的区别在于完全背包可以重复选择元素,所以递推时从前往后遍历。
定义一个dp数组dp[i]表示可以组成总金额i的组合总数,若i等于0则不需要选择硬币即可组合成i,所以初始化dp[0]为1,其他均为0.
当j>=coins[i]时,dp[j]=dp[j]+dp[j-coins[i]]
代码
class Solution {public int change(int amount, int[] coins) {int n=coins.length;int[] dp=new int[amount+1];dp[0]=1;for(int i=0;i<n;i++){for(int j=1;j<=amount;j++){if(j>=coins[i]){dp[j]=dp[j]+dp[j-coins[i]];}}}return dp[amount];}
}