- 题目要求:
-
思路:
- 画一个表格
- 可以求出数组中所有元素的和为 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]