厦门网站专业建设,海外推广电商,石家庄网站建设王道下拉棒,深圳坂田网站设计公司有哪些494. 目标和 - 力扣#xff08;LeetCode#xff09;
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a;
例如#xff0c;nums [2, 1] #xff0c;可以在 2…494. 目标和 - 力扣LeetCode
给你一个非负整数数组 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
思路整理可以将集合分为两个集合一个加法集合left一个减法集合right
可以求出加法集合left将问题转换为求出left这个集合。详细讲解看下文~
left:表示加法集合
right:表示减法集合left right sum
left - right target
left (sum target) / 2集合{1 1 1 1 1}分成left 和 right生成的target如下
left(加法集合) right(减法集合) target4 1 -33 2 12 3 -11 4 -3sum 5
left (sum target) / 2
(O_O)?
发现并没有target 2于是当target 2时left (25)/2 7/2 无法整除,
也就是 7 % 2 1 直接就 return 0 就好了表示找不出这样的集合能满足 left - right target
此时问题转化为求出left这个集合也就是说这个容器
问在这个集合里边的所有元素装满这个容器有多少种方法妙啊~有多少个元素能装满这个容器我们就能找到符合这个题目条件的多少种
组合。此时发现这有点类似背包问题。那么left就是背包的容量
集合{1 1 1 1 1}是物品集合例子 nums [1,2,1,3,1]target -2当这种情况的时候left3
1二维dp数组
dp[i][j] 表示在数组 nums 的前 i 个数中选取元素使得这些元素之和等于 j 的方案数
比如说我们要计算元素之和 等于 3 的方案数由于
0 3 3
1 2 3
2 1 3
所以我们可以把元素之和 等于 012的方案数分别计算出来然后再相加就可以得到元素之和等于3的方案数。 当nums[0]1时
nums[0]放不进去容量为0的背包 j0,jnums[0],那么dp[1][0] dp[0][0] 1
nums[0]放得进去容量为1、2、3的背包 j1,jnums[0],那么dp[1][1] dp[0][1] dp[0][1-nums[0]] 0 dp[0][0] 0 1 1 j2,jnums[0],那么dp[1][2] dp[0][2] dp[0][2-nums[0]] 0 dp[0][1] 0 0 0 j3,jnums[0],那么dp[1][3] dp[0][3] dp[0][3-nums[0]] 0 dp[0][2] 0 0 0
以此类推~ 思考
当 j nums[i-1]时
① dp[i][j] dp[i-1][j]; //copy当j nums[i-1]时
② dp[i][j] dp[i-1][j] dp[i-1][j-nums[i-1]];将①和②整合起来
dp[i][j] dp[i-1][j];
if(jnums[i-1]) {dp[i][j] dp[i-1][j-nums[i-1]];
}
// 二维dp数组
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;int n nums.size();int left 0,right 0;for(int i0;in;i) { sum nums[i];}if (abs(target) sum) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案left (sum target) / 2;vectorvectorint dp(n 1, vectorint(left 1));dp[0][0] 1;for (int i 1; i n; i) { // 物品for (int j 0; j left; j) { // 背包dp[i][j] dp[i - 1][j];if (j nums[i-1]) {dp[i][j] dp[i - 1][j - nums[i-1]];}}}return dp[n][left];}
}; 思考,压缩状态将二维dp数组 优化为 一维dp数组 将二维dp数组压缩成一维dp数组 重复利用实现滚动数组
dp[j] dp[j-nums[i]];dp[j] 装满容量为j的背包 有dp[j]种方法↑
dp[j-nums[i]] nums[i] dp[j-nums[i]] 1 dp[4] 凑成 dp[5]2 dp[3] 凑成 dp[5]3 dp[2] 凑成 dp[5]4 dp[1] 凑成 dp[5]5 dp[0] 凑成 dp[5]dp[5] dp[4] dp[3] dp[2] dp[1] dp[0]也就是dp[j] dp[j-nums[i]];初始化:dp[0] 1
集合{0} target 0 此时dp[0] 1
// 一维dp数组
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;int left 0,right 0;for(int i0;inums.size();i) { sum nums[i];}if (abs(target) sum) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案left (sum target) / 2;vectorint dp(left1,0);dp[0] 1;for(int i0;inums.size();i) { // 遍历物体for(int jleft;jnums[i];j--) { // 遍历背包dp[j] dp[j - nums[i]]; }}return dp[left];}
};
