Target Sum

这道题其实说不清算是个坐标还是接龙或者区间了，因为根据它的状态转移方程，它实际上只需要之前状态的两个点，但是这个题用由大到小的递归记忆化思路分析又非常自然，不过最后因为是用矩阵递推做出来的，还是归在坐标型里面了，此题其实思路非常清晰，当你需要一个dp[i][j]，j代表当前的S，i代表用前i个数，此时你需要的状态很明显可以看出来就是dp[i - 1][j - nums[i]]和dp[i - 1][j + nums[i]]，既然这个状态方程求出来了，实际也就很好处理了，但是此题有一个稍微有难度的地方在于你要看出来dp矩阵的横纵坐标是代表什么，横坐标不用说，数组长度而已，纵坐标在这里代表的是nums这个数组的总和减去这个总和乘以负一，这个长度实际上就是S有可能被凑成的上下界，如果S不在这个范围里面是不可能凑齐的，上下界拿到了之后再做这道题就简单了，状态方程上面已经讲了，下面是自己的代码，因为考虑了初始化等一些列小问题，速度比较慢，再放出一个Java答案做下对比吧

class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        n = len(nums)
        up = sum(nums)
        down = -up
        if S < down or S > up:
            return 0


        dp = [([0] * (up - down + 1)) for _ in xrange(n + 1)]
        for i in xrange(up - down + 1):                        # 纵坐标一定要从0开始递推
            if i + down == nums[0]:
                dp[1][i] += 1
            if i + down == -nums[0]:
                dp[1][i] += 1

        for i in xrange(2, n + 1):
            for j in xrange(up - down + 1):
                a, b = 0, 0
                if j + nums[i - 1] < up - down + 1:
                    a = dp[i - 1][j + nums[i - 1]]
                if j - nums[i - 1] >= 0:
                    b = dp[i - 1][j - nums[i - 1]]
                dp[i][j] = a + b

        return dp[n][S - down]

下面是答案的Java代码，思路是一样的，只是代码更干净而且进行了空间优化O(n)

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[] dp = new int[2001];
        dp[nums[0] + 1000] = 1;
        dp[-nums[0] + 1000] += 1;
        for (int i = 1; i < nums.length; i++) {
            int[] next = new int[2001];
            for (int sum = -1000; sum <= 1000; sum++) {
                if (dp[sum + 1000] > 0) {
                    next[sum + nums[i] + 1000] += dp[sum + 1000];
                    next[sum - nums[i] + 1000] += dp[sum + 1000];
                }
            }
            dp = next;
        }
        return S > 1000 ? 0 : dp[S + 1000];
    }
}