Leetcode Link: 494. 目标和 - 力扣（LeetCode）
题目
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。 返回可以通过上述方法构造的、运算结果等于target的不同 表达式 的数目。
解法一
思路：（我自己的思路）从暴力递归到动态规划
- 暴力递归
需要定义一个子函数，子函数输入的关键参数是：当前位置 idx 和当前的和 ssum，返回的是从[idx.. n]里，能够凑成 target 的结果的数量
只有两种情况：加当前位置的数或者减当前位置的数
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
res = self.process(target, nums, 0, 0)
return res
def process(self, target, nums, idx, ssum):
# base case
if idx == len(nums) and ssum == target:
return 1 #
if idx == len(nums) and ssum != target:
return 0
## 只有两种情况，结果为两种情况的和
p1 = self.process(target, nums, idx+1, ssum + nums[idx])
p2 = self.process(target, nums, idx+1, ssum - nums[idx])
return p1 + p2上面答案正确，但是会超时，下面改写成动态规划
显然是二维 dp
改写的过程中，需要注意的是其中一个轴的意义是”数字和”，那么如果范围就是全取正号和全取负号，这样范围就是 [-sum(nums), sum(nums)]。
由于实际写代码的时候不能有负数的 index，因此需要转化为正数。那么就需要时刻考虑到轴的 idx 和真实的和之间的关系
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
CONVERT = sum(nums)
# 行表示 数字的idx，列表示和，注意多出来一行
dp = [[0 for _ in range(2*sum(nums)+1)] for _ in range (len(nums)+1)]
# 根据base case填写初始值
for i in range(len(dp[0])):
if i == (target + CONVERT):
dp[len(nums)][i] = 1
else:
dp[len(nums)][i] = 0
for i in range(len(nums)-1, -1, -1): # 走行
for j in range(len(dp[0])): # 走列
true_sum = j - CONVERT # 真实值和索引之间的变换
# 下面是越界判断，但是在暴力递归中没有体现出来
j1 = true_sum + nums[i] + CONVERT
j2 = true_sum - nums[i] + CONVERT
if not 0 <= j1 < len(dp[0]):
dp[i][j] = dp[i+1][j2]
elif not 0 <= j2 < len(dp[0]):
dp[i][j] = dp[i+1][j1]
else:
dp[i][j] = dp[i+1][j1] + dp[i+1][j2]
return dp[0][CONVERT]解法二
思路：
题解：
解法三
思路：
题解：