Leetcode Combination IV问题中数组缓存记忆化解法超时，字典缓存正常运行的原因探究

Great question! Let's break down why your array-based memoization hits a time limit while the dictionary version works fine—even though both use memoization, their handling of "zero result" cases is the key difference.

The Core Issue: How Each Cache Handles Zero Values #

Let's look at how your two implementations treat a target that has no valid combinations (like target=99 in your test case, since none of the nums are ≤99):

1. Array-Based Cache (Your First Code)

Your dp array is initialized with [0]*(target+1), and dp[0] = 1. The recursive logic checks:

if dp[target]!=0:
    return dp[target]

Here's the problem: if a target has 0 valid combinations, dp[target] will stay 0 after calculation. Every subsequent call to recurse(nums, target, dp) will see dp[target] == 0 and re-run the entire loop over nums again—even though we already know the result is 0.

In your test case, this happens constantly. For example:

• When calculating 999-900=99, we loop through all 100+ nums, find none are ≤99, so dp[99] remains 0.
• Later, when calculating other paths that lead to targets like 8, 19, or 109 (all with no valid nums), we re-execute the full loop every time. This adds up to a ton of redundant work that drags down performance.

2. Dictionary-Based Cache (Your Second Code)

The dictionary memo stores all computed results, including 0. The logic checks:

if t in memo:
    return memo[t]

When we calculate a target with 0 combinations, we store memo[t] = 0. The next time we need that target's value, we just look it up in the dictionary and return 0 immediately—no need to re-run the loop.

This eliminates all redundant calculations for zero-result targets, which is exactly what saves you from TLE in your test case.

Quick Fix for Your Array-Based Code #

If you want to make the array version work, you need to track whether a target has been computed already (not just whether its result is non-zero). You could use a sentinel value (like -1) to mark uncomputed states:

def recurse(nums, target, dp):
    if dp[target] != -1:
        return dp[target]
    if target == 0:
        return 1
    res = 0
    for n in nums:
        if n <= target:
            res += recurse(nums, target - n, dp)
    dp[target] = res
    return res

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

This way, even if a target's result is 0, we mark it as computed (dp[target] = 0), so we never re-calculate it again.

Wrap-Up #

The dictionary naturally handles this because it only stores keys for targets we've actually computed—so checking if t in memo tells us if we've already done the work. The array, however, starts with all values set to 0, which conflates "uncomputed" with "result is 0". Fixing that distinction makes the array version just as efficient as the dictionary one.

内容的提问来源于stack exchange，提问作者skinnybb