Leetcode 上 Combination IV 的 Memoized 解决方案在数组用于缓存时给出 TLE

Question

在 Leetcode 上尝试解决 Combination IV 时，我想到了这个记忆解决方案：

def recurse(nums, target, dp):
        
    if dp[target]!=0:
        return dp[target]
    
    if target==0:
        return dp[0]

    for n in nums:
        if n<=target:
            dp[target] += recurse(nums, target-n, dp)
            
    return dp[target]

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        
        dp = [0]*(target+1)
        dp[0] = 1

        return recurse(nums, target, dp)

但这给了我一个超出时间限制的错误。

另一个记忆解决方案，使用字典而不是 dp 数组来缓存值，运行良好并且不超过时间限制。解决方法如下：

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        memo = {}
        def dfs(nums, t, memo):
            if t in memo:
                return memo[t]
            if t == 0:
                return 1
            if t < 0:
                return 0
            res = 0
            for i in nums:
                res += dfs(nums, t-i, memo)
            memo[t] = res
            return res
        return (dfs(nums, target, memo))

为什么使用字典而不是数组可以提高运行时间？这不像我们在遍历数组或字典，我们只是使用它们来存储和访问值.

编辑：我的代码崩溃的测试用例如下：

nums = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111]

目标=999

Answer 1

两个版本的代码不相同。在列表版本中，如果“缓存”值为 0，则继续递归。在字典版本中，如果当前键不在缓存中，则继续递归。当结果为 0 时，这会有所不同。例如，如果您尝试使用 nums=[2, 4, 6, 8, 10] 和 total=1001 的示例，列表版本中没有完成有用的缓存（因为每个结果为 0).

您可以通过将每个条目初始化为 None 而不是 0，并使用 None 作为标记值来确定是否未缓存结果来改进您的列表版本。

也更容易放弃缓存的想法，直接使用动态规划table。例如：

def ways(total, nums):
    r = [1] + [0] * total
    for i in range(1, total+1):
        r[i] = sum(r[i-n] for n in nums if i-n>=0)
    return r[total]

这显然在 O(total * len(nums)) 时间内运行。

这里没有必要（因为问题中的总数最多为 1000），但原则上您可以在迭代时仅保留 table 的最后 N 行（其中 N 是 table 的最大值数）。这将使用的 space 从 O(total) 减少到 O(max(nums))。

Leetcode 上 Combination IV 的 Memoized 解决方案在数组用于缓存时给出 TLE

Memoized solution to Combination IV on Leetcode gives TLE when an array is used for caching

python

memoization

python-3.x