题目描述
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
注意：
- 数组长度不会超过20，并且数组中的值全为正数；
- 初始数组的和不会超过1000；
- 保证返回的结果为32位整数。
解1
每个数字前都可以加正负号，那岂不是有 2^len(nums) 种可能，想到用动态规划来做，但和之前做的动态规划问题有不同，没能找到推导公式。
这篇博客 给出的解题思路很厉害：我们添加符号的过程事实上就把整个数组分为了两部分，正数部分 P， 负数部分 N，要满足 sum(P) + sum(N) == S ，同时 sum(P) - sum(N) == sum(nums) 。那么可得 sum(P) = (sum(nums) + S) // 2，把这个值记为 target 。这里注意 sum(nums) 不能小于 S，且两者之和必须是偶数。这样一来问题就转化为找到和为 target 的子序列个数。
新问题可以用动态规划来做。dp[i] 表示和为 i 的子序列个数，初始化 dp[0] 为1，啥都没有嘛可不就一种情况。
dp = [0] * (target+1)
dp[0] = 1
for num in nums:
for i in range(target, num-1, -1):
dp[i] += dp[i-num]
return dp[target]
解2
还是用动态规划来做，本题可类比背包问题，此时的背包容量是 [-sum(nums), sum(nums)]，有 len(nums) 个物体，装容量恰为 S 的方法数量。用二维数组 dp[len(nums)+1][(2*sum(nums)+1] 存储状态。dp[i][j] 表示到第 i 个物体时拾取容量为 j 的方法数。递推公式为：dp[i][j] += dp[i-1][j-nums[i-1]] dp[i][j] += dp[i-1][j+nums[i-1]]。代码如下：
for i in range(1, len(nums)+1):
for j in range(-sum_nums, sum_nums+1):
dp[i][j] += dp[i-1][j-nums[i-1]] if -sum_nums <= j-nums[i-1] <= sum_nums else 0
dp[i][j] += dp[i-1][j+nums[i-1]] if -sum_nums <= j+nums[i-1] <= sum_nums else 0
return dp[len(nums)][S]
总结
做题的时候感觉还是缺少数学思维，不能简化问题；再就是题目中有数组长度、数组和之类的提示，应该联想到怎么构造动态规划数组的。动态规划问题还得再看看，打算学习下背包九讲。ps：这类问题的时空复杂度还是蛮高的。