题意描述:
给你一个整数数组 nums
和一个整数 target
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
思路:
利用01背包,dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法。
递推公式:
dp[j] += dp[j - nums[i]]
组合问题的递推公式都是这样。
完整C++代码如下:
class Solution {
public: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;if((target + sum) % 2 == 1) return 0;int left = (sum + target) / 2;vector<int> dp(left + 1, 0);dp[0] = 1;for(int i = 0; i < nums.size(); i++){for(int j = left; j >= nums[i]; j--){dp[j] += dp[j - nums[i]];}}return dp[left];}
};