《Target Sum》题目分析

这道题可以用DP来解决，有点类似01背包问题。

首先每个数的大小是[1, 1000]，所以所有数的和的范围是[-100000, 100000]。

我们可以用f[i][j]表示前i个数中，和是(j-100000)一共有几种方法。

这里(j-100000)主要是考虑到数组下标不能是负数。

初始值是f[0][100000] = 0

递推方程大概是f[i][j] = f[i-1][j-A[j]] + f[i-1][j+A[j]]，需要考虑一下j-A[j]和j+A[j]的范围。

由于f[i][]的值全部是由f[i-1][]计算得来，所以可以用滚动数组优化空间复杂度。

整体的时间复杂度是O(NR)其中R是和的取值范围。