class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
int sum = accumulate(nums.begin(), nums.end(), 0);
if(target > sum || target < -sum) return 0;
int offset = sum;
vector<int> dp(2*offset+1, 0);
dp[0+offset] = 1;
for(int k = 0; k < n; ++k) {
auto tmp = dp;
for(int s = -sum; s <= sum; ++s) {
dp[s+offset] = 0;
if(s-nums[k]+offset>=0)
dp[s+offset] += tmp[s-nums[k]+offset];
if(s+nums[k]+offset<=2*offset)
dp[s+offset] += tmp[s+nums[k]+offset];
}
}
return dp[target+offset];
}
};
// dp[S]: number of ways to reach a sum S(offset added) after using k numbers
Submission II
class Solution {
int dp[25][2005];
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
const int offset = 1000;
nums.insert(nums.begin(), 0);
dp[0][0+offset] = 1;
for (int i = 1; i <= n; ++i) {
for(int s = -1000; s <= 1000; ++s) {
if (s-nums[i] <= 1000 && s-nums[i] >= -1000)
dp[i][s+offset] += dp[i-1][s-nums[i]+offset];
if (s+nums[i] <= 1000 && s+nums[i] >= -1000)
dp[i][s+offset] += dp[i-1][s+nums[i]+offset];
}
}
return dp[n][target+offset];
}
};
// dp[i][s]: for th ith num, how many ways to have a sum s.
// dp[i][s] = dp[i-1][s-nums[i]] + dp[i-1][s+nums[i]]
