# 1. 岛屿数量中 DFS、BFS、并查集三种解法在递归深度与并发场景下的取舍？ A DFS 递归深度可达网格大小，大网格可能栈溢出 ✓ 正确答案 B 并查集无法用于岛屿数量 C BFS 比 DFS 更易栈溢出 D 三种解法空间复杂度完全不同
# 2. 最长递增子序列中 O(n²) DP 到 O(n log n) 贪心+二分的思路跃迁？ A 替换策略是"用更大的尾元素替换" B tails 数组是递减的 C O(n²) DP 与 O(n log n) 复杂度相同 D O(n log n) 用 tails 数组存每种长度的最小尾元素，单调可二分 ✓ 正确答案
# 3. 课程表（拓扑排序）中 Kahn 算法与 DFS 染色法检测环的对比？ A DFS 染色法用双色标记 B Kahn 算法用入度归零的队列推进，出队数等于节点数则无环 ✓ 正确答案 C Kahn 算法无法检测环 D 染色法只能用于有向无环图
# 4. 网格类 BFS（最短路径、岛屿数量）与 Dijkstra 的转换条件是什么？ A Dijkstra 不能处理网格 B 边权不等时仍可用普通 BFS C 0-1 BFS 用普通队列 D 边权全为 1 时 BFS 即求最短路，是 Dijkstra 的特例 ✓ 正确答案
# 5. 零钱兑换（LeetCode 322）中为什么是完全背包而非 0-1 背包，初始化 INF 与 dp[0]=0 的边界意义？ A 硬币只能用一次，是 0-1 背包 B 硬币可无限使用，是完全背包，一维 dp 正序更新 ✓ 正确答案 C dp[0] 应初始化为 INF D 一维 dp 需倒序更新
# 6. 打家劫舍系列（线性/环形/树形）状态设计的演进关系？ A 树形问题用一维数组即可 B 环形问题拆成不含首与不含尾两个线性问题，取最大 ✓ 正确答案 C 线性转移为 dp[i]=max(dp[i-1], dp[i-2]+nums[i])，偷 i 则 i-1 也能偷 D 三题状态设计完全不同
# 7. 编辑距离 DP 的状态转移含义如何向面试官清晰解释？ A 边界 dp[0][j]=i B 删除对应 dp[i][j-1] C 相等时也要加 1 D 替换对应 dp[i-1][j-1]，删除对应 dp[i-1][j]，插入对应 dp[i][j-1] ✓ 正确答案
# 8. 求有向无环图的最长路径中拓扑排序 DP 与记忆化 DFS 的等价性？ A 两者复杂度不同 B 记忆化 DFS 无法避免重复计算 C 拓扑排序 DP 需要处理环 D 拓扑排序 DP 与记忆化 DFS 计算同一 DP，因为 DFS 后序在 DAG 上形成拓扑序 ✓ 正确答案
# 9. 0/1 背包与完全背包中一维滚动数组的遍历顺序为什么相反？ A 遍历顺序对结果无影响 B 两者都是正序 C 两者都是倒序 D 0/1 背包一维倒序，完全背包正序，区别在于是否允许重复使用同一物品 ✓ 正确答案
# 10. 动态规划的优化方向中滚动数组、状态压缩、单调队列与斜率优化何时用？ A 状态压缩用于转移含滑动窗口最值的场景 B 滚动数组利用只依赖相邻行的特性降低空间 ✓ 正确答案 C 单调队列用于子集状态 D 斜率优化用于降低空间
# 11. 爬楼梯（LeetCode 70）中为什么 f(n)=f(n-1)+f(n-2)，与斐波那契的滚动数组优化？ A 空间复杂度为 O(n) B 递推需要存整个数组，无法滚动 C f(n) 与斐波那契无关 D f(n)=f(n-1)+f(n-2)，因为最后一步只能从 n-1 或 n-2 迈入 ✓ 正确答案
# 12. 买卖股票的最佳时机（LeetCode 121/122）中一次交易维护历史最低价，多次交易用贪心累加正差价的依据？ A 121 需要记录所有买卖点 B 121 维护历史最低价算单次最大利润；122 贪心累加所有正差价 ✓ 正确答案 C 122 的贪心只在能买一次时正确 D 两者都需要 O(n) 空间
# 13. 单词拆分与完全背包的映射关系？ A 单词是组合型完全背包，外层物品 B 单词可重复、顺序重要，是排列型完全背包，外层容量、内层物品 ✓ 正确答案 C 单词不可重复使用 D dp[i] 表示前 i 个单词能否拼出
# 14. 不同路径（LeetCode 62/63）中答案等于组合数 C(m+n-2, m-1)，有障碍物时如何用 DP 处理？ A DP 无法处理边界障碍 B 有障碍时仍可用组合数 C 路径数 = C(m+n-2, n) D 无障路径数 = C(m+n-2, m-1)，有障碍时用 DP 使障碍格贡献 0 ✓ 正确答案
# 15. 边权为 0/1 的最短路中为什么 0-1 BFS 用双端队列能到 O(V+E)，与普通 BFS、Dijkstra 的关系？ A 0-1 BFS 需要优先队列 B 0 权边入队尾 C 0 权边入队首、1 权边入队尾，用双端队列达到 O(V+E) ✓ 正确答案 D 0-1 BFS 与普通 BFS 完全相同
# 16. 并查集如何支持"按秩合并+路径压缩"的时间复杂度证明（反阿克曼函数）？ A 路径压缩 + 按秩合并使单次操作摊还到 O(α(n)) ✓ 正确答案 B 只压缩不按秩合并在任何情况下都 O(α(n)) C 按秩合并不影响树高 D 路径压缩是可选优化，不影响复杂度
# 17. 完全平方数（LeetCode 279）中为什么是完全背包问题，dp[n]=min(dp[n-k*k])+1 的转移？ A 复杂度为 O(n) B 平方数只能用一次，是 0-1 背包 C dp[n] 只依赖 dp[n-1] D 平方数可重复使用，是完全背包，转移 dp[n]=min(dp[n-k²])+1 ✓ 正确答案
# 18. 最大正方形（LeetCode 221）中 dp[i][j]=min(上,左,左上)+1 的状态含义，为什么取三者最小？ A dp[i][j] 取上、左、左上三者最小值 +1，因为任一方向不足都会限制边长 ✓ 正确答案 B 取三者最大值 +1 C 只依赖上方 D dp[i][j] 表示以 (i,j) 为左上角的正方形
# 19. 跳跃游戏（LeetCode 55/45）中维护最远可达下标判断可行性，最少步数如何用“当前边界+下一边界”贪心？ A 55 需要 BFS B 45 需要枚举所有路径 C 55 维护最远可达下标判断可行性；45 用当前边界+下一边界贪心求最少步数 ✓ 正确答案 D 45 的贪心不保证最少步数
# 20. 最小路径和（LeetCode 64）中网格 DP 的边界初始化，与不同路径/最大正方形的统一视角？ A 与不同路径的转移完全相同 B 无需边界初始化 C 转移取上左最大值 D 首行首列需单独初始化（只能单向），中间取上左最小值 ✓ 正确答案
# 21. 分割等和子集（LeetCode 416）中如何把问题转化为 0-1 背包（目标和为总和一半），与零钱兑换的区别？ A 是完全背包，正序更新 B 转化为 0-1 背包（目标为总和一半），每个数只用一次，倒序更新 ✓ 正确答案 C 无需判断总和奇偶 D 与零钱兑换的背包类型相同
# 22. 记忆化搜索转 DP 的顺序推导中如何确定状态依赖方向（拓扑序）？ A 确定依赖方向后按"被依赖方先算"填表，通常按下标单调方向或拓扑序 ✓ 正确答案 B 转 DP 无需关心依赖顺序 C 记忆化搜索需要显式维护顺序 D 区间 DP 按大到小填表
# 23. 区间 DP 与状态压缩 DP 中典型问题与转移方程设计？ A 区间 DP 按区间长度递增填表，状态压缩 DP 用位掩码表示子集 ✓ 正确答案 B 区间 DP 用位掩码表示状态 C 状态压缩 DP 按长度递增 D 两者复杂度相同
# 24. 图的最短路径变体中带负权、多源、次短路与 A* 的适用场景？ A 多源必须跑多次单源 B Dijkstra 可处理负权 C 负权用 Bellman-Ford/SPFA，多源用虚拟源点，次短路用双值 Dijkstra ✓ 正确答案 D A* 无启发时比 Dijkstra 更慢
# 25. 状态压缩 DP 中旅行商问题的状压转移与位运算优化？ A 状态只需 mask 无需当前位置 B dp[mask][i] 表示已访问集合 mask 且当前在 i，转移枚举上一个城市 j ✓ 正确答案 C 复杂度为 O(n²) D 位运算用于判断集合成员但无法移除元素
# 26. 矩阵中的最长递增路径（LeetCode 329）中记忆化 DFS 的状态复用，为什么能避免重复计算？ A 从 (i,j) 出发的最长路径与到达方式无关，可缓存复用，每个格子只算一次 ✓ 正确答案 B 记忆化会重复计算同一格子 C 严格递增无法保证无环 D 复杂度为 O(n²·m²)
