LeetCode 494：将DFS +备忘转换为动态编程（DP）

Question

我正在尝试解决leetcode“目标总和”问题（https://leetcode.com/problems/target-sum/）。

我已经提出了这种自下而上的递归DFS +记忆化方法。

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:

        memo = {}
        def dfs(i, total):
            if i==len(nums) and total == S:
                return 1
            elif i == len(nums):
                return 0
            if (i,total) in memo:
                return memo[(i,total)]

            addition = dfs(i+1, total + nums[i])
            subtraction = dfs(i+1, total - nums[i])

            memo[(i,total)] = addition + subtraction

            return memo[(i,total)]

        return dfs(0,0)

现在我想将memo词典变成列表[[]]的列表，该列表将保留程序的状态。我曾尝试查看该解决方案，但无法将其与DFS + memoization关联。

我想逐步说明如何将此解决方案转换为DP解决方案。

Target Sum

Answer 1

我想迭代起来会更容易，更干净：

Python

from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if not nums or sum(nums) < target:
            return 0

        memo = {0: 1}
        for num in nums:
            temp = collections.defaultdict(int)
            for index, value in memo.items():
                temp[index + num] += value
                temp[index - num] += value
            memo = temp

        return memo[target]