题目
494.目标和
给你一个非负整数数组 nums
和一个整数 target
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
示例 1:
输入:nums = [1,1,1,1,1], target = 3 输出:5 解释:一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
示例 2:
输入:nums = [1], target = 1 输出:1
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
思路
先分析题意可知
将数组分成两个数组,分别为left和right
那么可得
left+right = sum. 式1
left-right = target。 式2
式1和式2合并后可得left=(sum+target)/2
target和sum两个都是固定的,那left就也固定了,题目就转换为从nums中求和为left的集合
问题就转化为,用nums装满容量为的背包,有几种方法。
这里的x,就是bagSize,也就是我们后面要求的背包容量。
大家看到(target + sum) / 2
应该担心计算的过程中向下取整有没有影响。
这么担心就对了,例如sum是5,target是2 的话其实就是无解的,所以:
if ((target + sum) % 2 == 1) return 0;
无法整除2就直接返回0表示无法满足
同时如果target 的绝对值已经大于sum,那么也是没有方案的。
if abs(target) > sum: return 0
动规五步曲:
1.确定dp数组(dp table)以及下标的含义
dp[j]表示容量为j的背包装满一共有dp[j]种方法
2.确定递推公式
dp[j] += dp[j-nums[i]]
3.dp数组如何初始化
dp[0] = 1
4.确定遍历顺序
与0-1背包的一维数组一样即可
5.举例推导dp数组
代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
nums_sum = sum(nums)
if abs(target) > nums_sum :
return 0
if (nums_sum+target)%2 == 1:
return 0
target = (nums_sum+target)//2
dp = [0]*(target+1)
dp[0] = 1
for i in range(len(nums)):
for j in range(target,nums[i]-1,-1):
dp[j] += dp[j-nums[i]]
return dp[-1]