邢台县建设局网站,鲜花网站建设文档,wordpress用户前端,石家庄个人建网站给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a; 例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 #xff0c;在 1 之前添加 - #xff0c;然…给你一个非负整数数组 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
题目大意在每个数可正可负的情况下计算所有数和为target的表达式数目。
分析
1设所有数都是正数时的和为sum添加负号的元素的绝对值和为tar使(sum-tar)-tartarget则tar(sum-target)/2
2由1可知当(sum-target)%21或者sum-target0时不可能有和为target的表达式返回0即可否则在原数组中选取若干元素使其所选元素的绝对值和为tar即可满足表达式和为target因此所求的表达式数目为从数组中选取若干元素使绝对值和为tar的方案数
3为求从数组中选取若干元素使绝对值和为tar的方案数可设二维数组dpdp[i][j]表示从数组中前i个元素中选取若干元素使绝对值和为j的方案数。则当jnums[i]时dp[i][j]dp[i-1][j]当jnums[i]时dp[i][j]dp[i-1][j]dp[i-1][j-nums[i]]。最终dp[nums.size()][tar]的值即为从数组中选择若干元素使绝对值和为tar的方案数返回即可
4由于dp数组每一行的元素只与上一行的元素有关因此可对dp数组进行降维则dp[k]表示遍历第i个元素时从前i-1个元素中选取若干元素使绝对值和为k的方案数。
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int Nnums.size(),sum0;for(int ele:nums) sumele;int diffsum-target,tardiff/2;if(diff0||diff%2) return 0;vectorint dp(tar1,0);dp[0]1;for(int ele:nums){for(int ktar;kele;--k) dp[k]dp[k-ele];}return dp[tar];}
};
