共计 1467 个字符，预计需要花费 4 分钟才能阅读完成。
- 题目要求：
-
思路：
- 画一个表格
- 可以求出数组中所有元素的和为 5，所以画一个（5*2+1）len(nums)的表格（也就是一个二维数组）
- -5~5 表示把这个数组每一个元素加上或减去得到结果值的所有可能
- 从 [-1 -1 -1 -1 -1] 到[+1 +1 +1 +1 +1]的所有可能
- 遍历数组，当遍历到数组下标为 0 的元素时，也就是第一个 1，它与加号减号的组合有两种：1 和 -1，所以得到 - 1 的方法有 1 种，得到 1 的方法也有一种
- 当遍历到数组下标为 1 的元素时，前面已经得到的可能的结果值为 - 1 和 1，那么在这个基础上，新加入新的 1 与加号减号的组合，可能得到 -2（-1-1），可能得到 0（-1+ 1 或 +1-1），可能得到 2（+1+1），所以在 - 2 的位置有一种方法，在 0 的位置有 2 种，在 1 的位置有 1 种
- 依次遍历，遍历到最后，找到目标值所对应的列的最后一行，也就是 3 所对应的有 5 中方法，返回 5 即可
-
要特殊注意：
- 当数组的第一个元素为 0 时，应初始化 0 的位置方法为 2，因为 0 +0=0，0-0=0
- 核心代码：
dp = [[0 for i in range(2 * total + 1)] for j in range(len(nums))]
# 如果数组的第一个元素为 0，那么 + 0 或是 -0，结果都为 0
if nums[0] == 0:
dp[0][total] = 2
else:
# total 是数组元素的和，也是 dp 的行中，元素值为 0 的元素的下标
dp[0][total + nums[0]] = 1
dp[0][total - nums[0]] = 1
for i in range(1, len(dp)):
for j in range(len(dp[0])):
# 注意边界
# 在第一个图中，dp[4][0]的当前元素值是 1，对应的目标值是 -5，那么 - 5 加上或减去 1 可能是上一行得到的值，但是要注意 -5- 1 也就是 - 6 不在考虑范围内
# left 和 right 都初始化为 0，是因为在表格也就是二维数组中，0 所在的列所对应的目标值是给定数组的所有元素可能得到的最小值，是一个极值，所以不到最后一行，也就是不遍历到最后一个数组元素是得不到这个值的，也就是，所有行的下标为 0 的位置（所有行的起始位置）的方法数一定是 0，所以当 left 或 right 越界了，没有被赋新的值时，不会影响计算方法数
left, right = 0, 0
if j - nums[i] >= 0:
left = j - nums[i]
if j + nums[i] < 2 * total + 1:
right = j + nums[i]
dp[i][j] = dp[i - 1][left] + dp[i - 1][right]
return dp[-1][total + S]- 完整代码：
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
total = sum(nums)
if total < S:
return 0
dp = [[0 for i in range(2 * total + 1)] for j in range(len(nums))]
if nums[0] == 0:
dp[0][total] = 2
else:
dp[0][total + nums[0]] = 1
dp[0][total - nums[0]] = 1
for i in range(1, len(dp)):
for j in range(len(dp[0])):
left, right = 0, 0
if j - nums[i] >= 0:
left = j - nums[i]
if j + nums[i] < 2 * total + 1:
right = j + nums[i]
dp[i][j] = dp[i - 1][left] + dp[i - 1][right]
return dp[-1][total + S]
正文完
