leetcode 494 目标和
z
 2020-08-23 14:53:01    

给定一个非负整数数组，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 位整数存下。
链接：https://leetcode-cn.com/problems/target-sum

  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        return self.helper(nums, S, 0, len(nums), [])
    
    def helper(self, nums, S, start, end, t):
        if start == end:
            if S == sum(t):
                return 1
            return 0
        ans = 0
        t.append(nums[start])
        ans += self.helper(nums, S, start+1, end, t)
        t.pop(-1)
        t.append(nums[start] * (-1))
        ans += self.helper(nums, S, start+1, end, t)
        t.pop(-1)
        return ans
  • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        # p - n = S
        # p - n + n = S + n
        # p + n = S + 2n
        # sum(nums) = S + 2n
        # n = (sum(nums) - S)/2
        N = sum(nums)
        if S > N or (N-S)%2:
            return 0
        target = (N - S)/2
        dp = [1] + [0] * target
        
        for i in nums:
            for j in range(target, i-1, -1):
                    dp[j] += dp[j-i]
        return dp[-1]

但是，通常而言，不会考虑到这么特殊的情况，还有一种比较通用的dp，应该是能想到的。

  • 动态规划2
1
2
# 可以理解为，dp[i][j]表示的是到第i个元素，sum为j的组合数
# 那么: dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]