用记忆化搜索写 0/1 背包：状态 dfs(i, j) 表示只考虑前 i 件物品、剩余容量 j 时能拿到的最大价值，转移为 dfs(i,j) = max(dfs(i-1,j), dfs(i-1, j-w[i]) + v[i])（v[i] >= 0）。你把 memo[i][j] 全部初始化为 0，并用 if (memo[i][j] != 0) return memo[i][j]; 来判断"这个状态算过没有"。请说明这个写法哪里有问题、什么时候会出错，并给出正确的改法。

面试官在考什么

判断候选人有没有真的自己写过记忆化搜索，知不知道"用某个值表示未计算"这个约定成立的前提是什么，以及剪枝失效会带来什么后果。

记忆化搜索

回答框架 · 前两步

1. 会出错：当某个状态的合法答案恰好是 0（比如剩余容量放不下任何物品、或者所有能选的物品价值都是 0）时，memo 里的 0 既表示"算过了，答案是 0"，又表示"没算过"，用 != 0 判断会把它当成没算过。
2. 后果是这些状态会被反复递归计算，记忆化剪枝失效，最坏情况下递归树重新膨胀，复杂度从 O(n*W) 严重退化（可能接近指数级）而超时。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 01 背包场景：n=1000 件物品，背包容量 W=100000，每件物品重量 w_i、价值 v_i，每件最多选 1 件，求最大总价值。你写一维数组 DP，代码里容量循环写成 for (int j=W; j>=w[i]; --j)，而不是 for (int j=w[i]; j<=W; ++j)。请解释这两种写法在 01 背包和完全背包下分别会得到什么结果，为什么？如果把条件改成每种物品最多选 2 件，你会怎么改？
• 0-1 背包精确求解。实例 A：n=100，W=10^9，每个 w_i 可达 10^9，v_i<=1000；实例 B：n=40，W=10^9，w_i 和 v_i 可达 10^12。单次预算 1 秒。你会分别选什么算法？请给出状态定义、复杂度，并说明为什么不能都写成 dp[W]。
• 你在做一个离线批处理调度器：每天凌晨要在一台 128 核的机器上，从 N=2000 个待跑任务里挑一个子集执行，每个任务有 CPU 需求 w_i（1~200 的整数核）和业务收益 v_i，目标是总收益最大。需求要求最终输出被选中的任务清单，而不是只输出最优收益值，且整个求解要在 5 秒内完成。同事给的方案是标准 0/1 背包 DP。请说明你会怎么实现（状态定义、空间处理、方案还原），并回答：如果第二天任务数变成 200000、机器换成 10000 核的聚合池，同一套代码还能不能撑住，你会怎么改。
• 有 N 件物品，第 i 件体积 w[i]、价值 v[i]，每件物品只能用一次，背包容量为 W。用一维数组 f[0..W] 写 0/1 背包时，内层容量循环必须写成 for (j = W; j >= w[i]; --j)。请说明为什么必须倒序，并自己举一个具体的数值例子（给出 w、v、W），把正序循环时数组被更新的过程一步步算出来，说明会出什么错。
• 给定长度为 n=500 的数组 a，每次可以合并相邻两个数，代价为两数之和，合并后新数放回原位置。求把所有数合并成一个数的最小总代价。你定义的状态是什么？转移方程怎么写？为什么枚举区间长度而不是只枚举起点？时间、空间复杂度各是多少？如果数组是环形的，即首尾也相邻，你怎么处理？
• 给定字符串 s，长度 n=5000，求最长回文子序列长度。区间 DP 转移是 s[i]==s[j] 时 dp[i][j]=dp[i+1][j-1]+2，否则 max(dp[i+1][j], dp[i][j-1])。O(n^2) 时间约 25e6 可接受，但 dp[n][n] 的 int 约 100MB，内存限制 64MB。你会怎么设计枚举顺序和滚动数组？如果还要求输出任意一个最长回文子序列，滚动数组还缺什么信息？