LeetCode#494

LeetCode#494目标和

题目链接
题目大意：给你一个n个数的数组和一个目标数，你可以选择给数组中的每个数加上+或-，最后求和，问你一共有多少种组合可以使数组的和达到目标数。
这题其实直接暴力递归回溯也可以，不过最近在练dp…乍一看有点像01背包，区别是01背包是每个物品选或不选，而这个是每个数要选择+或者-，我们设dp[i][j]，i表示使用了数组的前i个数，j表示前i个数的加和，dp数组的值表示用前i个数组成j有几种组合。
因为我们只能选择第i个数是+还是-，所以状态转移方程就是：

dp[i][j] = dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]//就是当前这个数选择+或-的两种情况加和

然后因为加和可能出现为负数的情况，所以我们可以在第二维(j)预加一个值，保证数组不越界（用python当然就没这个问题了。。。）
最后再加亿点细节，代码就出来了：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        vector<vector<int> >dp(30,vector<int>(5000));
        int len = nums.size();
        int sum = 0;
        for(int i = 0 ;i < len ; i++)//预先算一下最大跑到的值和最小跑到的值
            sum+=abs(nums[i]);
        if(S > sum || S < -sum)//超出范围直接返回
            return 0;
        dp[0][nums[0]+2000]=1;//初始化，+2000是因为题目说了加和最大值不超过1000
        dp[0][-nums[0]+2000]+=1;//可能有0的情况，所以是+=
        for(int i = 1 ; i < len ; i++)
            for(int j = -sum ; j <= sum ; j++)
                dp[i][j+2000] = dp[i-1][j-nums[i]+2000]+dp[i-1][j+nums[i]+2000];
        return dp[len-1][S+2000];
    }
};