leetcode 494. 目标数

题目描述：

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], 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位整数。

思路分析：

思路一：用递归深搜，效率很低。存在重复计算。

思路二：动态规划。由于题目中说明了不会超过1000，利用一个2000的数组来存正数和负数。

代码：

思路一：

 1 class Solution {
 2 public:
 3     long long dfs(vector<int>& nums, long long S, int start)
 4     {
 5         int n = nums.size();
 6         if(start >= n)
 7             return 0;
 8         if(start == n-1)
 9         {
10             if(S == nums[start] || S== -nums[start])
11             {
12                 if(nums[start]==0)
13                     return 2;
14                 else
15                     return 1;
16             }
17             else
18                 return 0;
19         }
20         else
21         {
22             long long path1 = dfs(nums, S-nums[start], start+1);
23             long long path2 = dfs(nums, S+nums[start], start+1);
24             return path1+path2;
25         }
26     }
27     int findTargetSumWays(vector<int>& nums, int S) {
28         if(nums.size()==0)
29             return 0;
30         long long ans = dfs(nums, S, 0);
31         return ans;
32     }
33 };

思路二：

 1 class Solution {
 2 public:
 3     int findTargetSumWays(vector<int>& nums, int S) {
 4         if(nums.size()==0)
 5             return 0;
 6         int pre[2001], now[2001];
 7         memset(pre, 0, sizeof(pre));
 8         memset(now, 0, sizeof(now));
 9         pre[1000]=1;
10         for(int i=0; i<nums.size(); i++)
11         {
12             for(int j=0; j<2001; j++)
13             {
14                 if(pre[j]!=0)
15                 {
16                     now[j+nums[i]] += pre[j];
17                     now[j-nums[i]] += pre[j];
18                 }
19             }
20             for(int j=0; j<2001; j++)
21             {
22                 pre[j] = now[j];
23                 now[j] = 0;
24             }
25         }
26         if(S>1000)
27             return 0;
28         else
29             return pre[1000+S];
30     }
31 };