问题描述
思路
这是一道关于选择的题目，也就是对于每一个数，都有选+还是选-两种选择。 首先确定状态，设数组的位置为变量i，表示考虑数组的第0到i的数，target的数值为j 很容易就可以找出状态方程 dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]];当然要注意边界情况 然后这个题目很容易犯错的一点就是，二维数组的列要开所有元素和的两倍加1那么大，表示target从-sum到sum。而且当S大于sum的时候，是没有解的。
代码
class Solution {
public:
int findTargetSumWays(vector
<int>& nums
, int S
) {
int n
=nums
.size(),sum
=0;
for(int i
=0;i
<n
;i
++) {
sum
+=nums
[i
];
}
if(S
>sum
) return 0;
vector
<vector
<int> > dp(n
,vector
<int> (2*sum
+1,0));
if(nums
[0]==0) dp
[0][sum
]=2;
else dp
[0][sum
+nums
[0]]=dp
[0][sum
-nums
[0]]=1;
for(int i
=1;i
<n
;i
++) {
for(int j
=0;j
<=2*sum
;j
++) {
int a
=0,b
=0;
if(j
-nums
[i
]>=0) a
=dp
[i
-1][j
-nums
[i
]];
if(j
+nums
[i
]<=sum
*2) b
=dp
[i
-1][j
+nums
[i
]];
dp
[i
][j
]=a
+b
;
}
}
return dp
[n
-1][sum
+S
];
}
};
