C++刷LeetCode（494. 目标和）【动态规划】
题目描述：给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: , S: 3
输出：5
解释：
-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
一共有5种方法让最终目标和为3。
提示：
数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for(auto cha : nums)sum += cha;
if(abs(S) > sum)return 0;
int t = sum * 2 + 1, len = nums.size();
vector<vector<int> > dp(len, vector<int>(t, 0));
//初始化
if(nums == 0){
dp = 2;
}else{
dp] = 1;
dp] = 1;
}
for(int i = 1; i < len; i++){
for(int j = 0; j < t; j++){
int l = (j - nums) >= 0 ? j - nums : 0;
int r = (j + nums) < t ? j + nums : 0;//t这里是位置
dp = dp + dp;
}
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/target-sum/solution/dong-tai-gui-hua-si-kao-quan-guo-cheng-by-keepal/
页:
[1]