LeetCode 494. 目标和

题目

给你一个整数数组 nums 和一个整数 target。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

例：
输入：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

方法：动态规划

按照之前的思路，应该将数组 nums 分割成两部分，一部分作为减数，另一部分作为被减数，两组元素相减得到 target

• sumValue 表示数组 nums 所有元素和
• 若目标和 target 的绝对值大于数组的所有元素和 sumValue，即所有元素相加或相减仍达不到 target，则表示表达式的数目一定为零；若两组元素的差无论怎样均无法得到 target，则表示表达式的数目一定为零
• bagSize 表示减数
• dp[j] 表示填满容量为 j 的背包，有 dp[j] 种方法。初始化 dp[0] 为 1，表示想要填满容量为零的背包，共有一种方法
• 外部循环，对数组进行正序遍历；内部循环，对背包容量进行倒序遍历

• 递推公式：因为求的是不同表达式的数目，所以应该把所有的可能性相加

  
  

class Solution(object):
    def findTargetSumWays(self, nums, target):
        sumValue = sum(nums)
        if abs(target) > sumValue or (sumValue + target) % 2 == 1:
            return 0
        bagSize = (sumValue + target) // 2
        dp = [0] * (bagSize + 1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(bagSize, nums[i] - 1, -1):
                dp[j] += dp[j-nums[i]]
        return dp[bagSize]

例：
nums = [1,1,1,1,1], target = 3

参考

代码相关：https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html