↓Skip to main content
  1. Posts/

LeetCode-494 目标和

·1 min·
Table of Contents

LeetCode-494 目标和 #

Solution 1 #

添加 $+$ 号的元素和为 $pos$, 添加 $-$ 号的元素和为 $neg$, 那么有 $target = pos - neg = total - 2neg$ . 转化为选取一些元素使得总和等于 $neg$ , 这是一个背包问题, 用动态规划解决.

代码如下:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:    
        tot = sum(nums)
        if tot < target or (tot - target) & 1:
            return 0
        n = len(nums)
        tgt = (tot - target) // 2
        dp = [[0 for _ in range(tgt + 1)] for _ in range(n)]
        dp[0][0] = 1
        if nums[0] <= tgt:
            dp[0][nums[0]] += 1
        for i in range(1, n):
            for j in range(tgt + 1):
                dp[i][j] = dp[i - 1][j]
                if j - nums[i] >= 0:
                    dp[i][j] += dp[i - 1][j - nums[i]]
        return dp[n - 1][tgt]