本文揭示了 leetcode 518 题常见递归+记忆化实现中因未正确更新 dp 表导致 tle 的核心原因，并通过代码对比与原理分析，说明如何确保记忆化真正生效。
本文揭示了 leetcode 518 题常见递归+记忆化实现中因未正确更新 dp 表导致 tle 的核心原因，并通过代码对比与原理分析，说明如何确保记忆化真正生效。
在解决「Coin Change II」（求组成目标金额的硬币组合数）问题时，采用带记忆化的深度优先搜索（DFS + memoization）是一种直观思路。但实践中，仅声明 DP 数组并检查缓存是不够的——必须确保每次计算结果都写回 DP 表，否则记忆化形同虚设，时间复杂度将退化为指数级。
我们来看原始低效版本的关键缺陷：
public int func(int[] arr, int sum, int i, int[][] dp) {
if (i >= arr.length) return 0;
if (sum == 0) return 1;
if (sum < 0) return 0;
if (dp[i][sum] != -1) return dp[i][sum]; // ✅ 检查缓存（正确）
int t = func(arr, sum - arr[i], i, dp); // 选当前硬币（可重复选）
int nt = func(arr, sum, i + 1, dp); // 不选当前硬币（换下一个）
return t + nt; // ❌ 错误：未写入 dp[i][sum]，下次调用仍会重复计算！
}该实现虽在入口处检查 dp[i][sum]，却在返回前遗漏了对 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 表，与第二个高效版本保持一致：
public int func(int[] arr, int sum, int i, int[][] dp) {
if (i >= arr.length) return 0;
if (sum == 0) return 1;
if (sum < 0) return 0;
if (dp[i][sum] != -1) return dp[i][sum];
int t = func(arr, sum - arr[i], i, dp);
int nt = func(arr, sum, i + 1, dp);
dp[i][sum] = t + nt; // ✅ 关键修复：写回结果
return dp[i][sum];
}? 为什么第二个版本“碰巧”高效？
它采用“从start开始遍历所有后续硬币”的递归逻辑，并在循环结束后统一赋值dp[start][sum] = s。虽然结构不同，但其严格保证每个状态只计算一次且结果必存入 DP 表，因此成功规避了重复计算。
? 额外建议：优化空间与逻辑清晰性
- 使用
Integer[][] dp可避免-1初始化歧义（null明确表示未计算）； - 更推荐标准的二维 DP 迭代解法（外层遍历硬币，内层遍历金额），时间
O(n×amount)、空间O(amount)，无递归开销且逻辑更稳健：
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1; // 金额0有1种组合（空集）
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}总结：记忆化递归的正确性不在于“是否声明了 DP 数组”，而在于每个子问题的结果是否被可靠地缓存并复用。漏写 dp[i][sum] = result 是导致 TLE 的典型低级错误，务必在返回前完成赋值。
