动态规划-leetcode-494

​​0️⃣python数据结构与算法学习路线​​ 学习内容：

• 基本算法：枚举、排序、搜索、递归、分治、优先搜索、贪心、双指针、动态规划等…
• 数据结构：字符串(string)、列表(list)、元组(tuple)、字典(dictionary)、集合(set)、数组、队列、栈、树、图、堆等…

题目：

给定一个非负整数数组，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。

解题思路：

算法实现：

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        nums_sum = sum(nums)
        if (S + nums_sum) % 2 == 1 or S > nums_sum:
            return 0
        nums_sum = (S + nums_sum) // 2
        dp = [0 for _ in range(nums_sum + 1)]
        dp[0] = 1
        for n in nums:
            for i in range(nums_sum, n - 1, -1):
                dp[i] += dp[i - n]
        return dp[nums_sum]

出现问题：

没想到(S + nums_sum) % 2