本文揭示了 leetcode 518 题常见递归+记忆化实现中因未正确更新 dp 表导致 tle 的核心原因，并通过代码对比与原理分析，说明如何确保记忆化真正生效。
本文揭示了 leetcode 518 题常见递归+记忆化实现中因未正确更新 dp 表导致 tle 的核心原因，并通过代码对比与原理分析，说明如何确保记忆化真正生效。
在解决「Coin Change II」（求组成目标金额的硬币组合数）问题时，采用带记忆化的深度优先搜索（DFS + memoization）是一种直观思路。但实践中，仅声明 DP 数组并检查缓存是不够的——必须确保每次计算结果都写回 DP 表，否则记忆化形同虚设，时间复杂度将退化为指数级。
我们来看原始低效版本的关键缺陷：
dp[i][sum]
- 同一
(i, sum)状态可能被反复递归计算数十甚至数百次； - 对于
amount = 500、coins = [3,5,7,8,9,10,11]这类输入，状态空间虽为O(n × amount) = 7×501 ≈ 3500，但无有效缓存时实际调用次数呈指数爆炸（如func(..., 500, 0)→func(..., 497, 0)→func(..., 494, 0)…），远超时限。
✅ 正确做法是：在计算完成后立即写入 DP 表，与第二个高效版本保持一致：
start
- 使用
Integer[][] dp可避免-1初始化歧义（null明确表示未计算）； - 更推荐标准的二维 DP 迭代解法（外层遍历硬币，内层遍历金额），时间
O(n×amount)、空间O(amount)，无递归开销且逻辑更稳健：
dp[i][sum] = result
