[494][中等][动态规划][背包] 目标和

题目描述

494. 目标和

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。

提示：

• 数组非空，且长度不会超过 20 。

• 初始的数组的和不会超过 1000 。

• 保证返回的最终结果能被 32 位整数存下。

解题思路

这种题目都可以转换成将原数组拆分成两个数组, 使得一个数组之和恰好为X的题目. 因此是标准的01背包问题.

题目中物品就是原数组中的元素. 本题的背包限制, 即一个数组的和的值可以这样求:

假设所有元素和为sum，所有添加正号的元素的和为A，所有添加负号的元素和为B，则有sum = A + B 且 S = A - B，解方程得A = (sum + S)/2。即题目转换成：从数组中选取一些元素使和恰好为(sum + S) / 2.

由于本题是求方法数, 因此dp全部初始化为0, 只有dp[0]初始化为1. 状态转移公式中的max也要变为sum.

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        total = sum(nums)
        if total < S or total < -S:
            return 0
        if (total + S) % 2:
            return 0

        target = (total + S) // 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] + dp[j - nums[i]]
        return dp[-1]