搜索、DP 与图高频 - 面试题

#

★★★

1. 岛屿数量中 DFS、BFS、并查集三种解法在递归深度与并发场景下的取舍？

问题

求解岛屿数量，比较 DFS、BFS、并查集三种解法在递归深度与并发场景下的取舍？

考察点

DFS 递归深浅、栈溢出风险
BFS 队列、无栈溢出
并查集可并行合并

答案

DFS：递归洪泛，代码简洁，但递归深度可达网格大小，大网格可能栈溢出（可改显式栈）。BFS：用队列层序洪泛，无递归栈溢出风险，适合大网格。并查集：把每个陆地格子作为节点，相邻陆地合并，最后统计连通分量数；适合并行（各区域可独立合并后 union），也能处理增量/动态连接。取舍：网格小用 DFS 最简；网格大担心栈深用 BFS；需并行或动态维护用并查集。三者时间都 O(n×m)，并查集空间略大（需 parent 数组）。

解析

三种解法是"连通分量"的三种视角：DFS/BFS 是显式/隐式洪泛，并查集是离线合并。DFS 的栈深是隐患，BFS 省心，并查集利于并行。选型取决于网格规模与并发需求。

示例代码

// 并查集法
int numIslandsUF(char[][] g) {
    int m = g.length, n = g[0].length;
    int[] parent = new int[m * n];
    Arrays.fill(parent, -1);
    int cnt = 0;
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
        if (g[i][j] == '1') { parent[i * n + j] = i * n + j; cnt++; }
    }
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
        if (g[i][j] == '1') {
            if (i + 1 < m && g[i + 1][j] == '1') if (union(parent, i * n + j, (i + 1) * n + j)) cnt--;
            if (j + 1 < n && g[i][j + 1] == '1') if (union(parent, i * n + j, i * n + j + 1)) cnt--;
        }
    return cnt;
}

#

★★★

2. 最长递增子序列中 O(n²) DP 到 O(n log n) 贪心+二分的思路跃迁？

问题

求最长递增子序列，说明从 O(n²) DP 到 O(n log n) 贪心+二分的思路跃迁？

考察点

O(n²) DP：dp[i]=max(dp[j])+1
O(n log n)：维护"最小尾元素"数组 tails
二分替换 + 贪心保证最小尾

答案

O(n²) DP：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度，转移 dp[i]=max(dp[j])+1（j<i 且 nums[j]<nums[i]），O(n²)。O(n log n)：贪心+二分——维护 tails 数组，tails[k] 表示长度为 k+1 的递增子序列的最小可能尾元素。遍历每个数 x，用二分在 tails 中找到第一个 ≥x 的位置 pos，更新 tails[pos]=x（贪心：用更小的尾元素替换，利于后续扩展），若 pos 超出当前长度则追加。最终 tails 长度即 LIS 长度。跃迁：从"每元素扫描所有前驱"（O(n²)）到"用二分在有序 tails 中定位"（O(n log n)），核心是"tails 保持有序"让定位变二分。

解析

思路跃迁的关键是状态重定义：DP 存"以 i 结尾的长度"，贪心存"每种长度的最小尾元素"。tails 因前缀最小尾而单调递增，故可二分。替换策略"贪心保最小尾"保证最优。这是"DP 状态重设计 + 二分"的经典优化。

示例代码

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int len = 0;
    for (int x : nums) {
        int l = 0, r = len;
        while (l < r) { int m = (l + r) / 2; if (tails[m] < x) l = m + 1; else r = m; }
        tails[l] = x; // 替换第一个 >= x 的位置
        if (l == len) len++;
    }
    return len;
}

#

★★★

3. 课程表（拓扑排序）中 Kahn 算法与 DFS 染色法检测环的对比？

问题

判断课程能否完成（拓扑排序），对比 Kahn 算法与 DFS 染色法检测环？

考察点

Kahn 算法：入度 + 队列
DFS 染色法：三色标记环
两者检测环的等价性

答案

Kahn 算法：计算每个节点入度，把入度为 0 的节点入队，每次出队并减少其邻居入度，入度为 0 的邻居入队。若最终出队节点数==总节点数则无环（可完成），否则有环（剩余的节点间成环）。复杂度 O(V+E)。DFS 染色法：三色（0 未访问、1 在递归栈中、2 完成）。DFS 时若遇到"在递归栈中"的节点即为环。遍历所有节点，若访问到灰色节点则返回有环。复杂度 O(V+E)。对比：Kahn 是 BFS 式（入度驱动），DFS 染色是递归式（栈上检测）；两者都能检测环，Kahn 还能给出拓扑序，DFS 染色更适合"递归中天然带深度"的场景。有环检测：Kahn 看计数，染色看灰色。

解析

Kahn 与染色是拓扑排序/环检测的两种标准路径，分别基于 BFS 与 DFS。Kahn 用入度归零推进，染色用递归栈回退。选型看习惯与是否需拓扑序：需拓扑序用 Kahn，递归场景用染色。

示例代码

// Kahn 算法
boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] indeg = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
    int cnt = 0;
    while (!q.isEmpty()) { int u = q.poll(); cnt++; for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v); }
    return cnt == numCourses; // 无环
}

#

★★★

4. 网格类 BFS（最短路径、岛屿数量）与 Dijkstra 的转换条件是什么？

问题

说明网格类 BFS 与 Dijkstra 的转换条件，何时用 BFS、何时用 Dijkstra？

考察点

BFS 适用于边权相等的最短路
Dijkstra 适用于非负权
网格边权为 1 时 BFS 即最短路

答案

BFS 适用于"所有边权相等"（如网格中每步代价为 1）的最短路，此时 BFS 的层序天然给出最短路径，复杂度 O(V+E)。当网格中移动代价不同（如陆地 1、水域 2，或绕路代价不等）时，BFS 不再适用，需 Dijkstra（非负权）或 0-1 BFS（权为 0/1）。转换条件：边权都相等→BFS；边权非负且不等→Dijkstra；边权 0/1→0-1 BFS（双端队列）。网格最短路是最典型的转换场景：BFS 是 Dijkstra 在"边权为 1"时的退化特例（Dijkstra 的优先队列退化为普通队列）。

解析

BFS 与 Dijkstra 的本质关系是"BFS 是 Dijkstra 在边权全 1 时的特例"。判断用哪个看边权是否一致：一致用 BFS（更简单、无 log 开销），不一致但非负用 Dijkstra。0-1 BFS 是中间态，用双端队列把 Dijkstra 的 log 降到 O(1)。

示例代码

// 网格 BFS 最短路径（边权 1）
int bfs(int[][] grid, int[] start, int[] end) {
    Deque<int[]> q = new ArrayDeque<>();
    // dist 数组记录最短距离，层序扩展
    int[][] dist = new int[grid.length][grid[0].length];
    // 初始化 INF，start 为 0，BFS 层序松弛
    return dist[end[0]][end[1]];
}

#

★★★

5. 零钱兑换（LeetCode 322）中为什么是完全背包而非 0-1 背包，初始化 INF 与 dp[0]=0 的边界意义？

问题

零钱兑换，说明为什么是完全背包而非 0-1 背包，以及初始化 INF 与 dp[0]=0 的边界意义？

考察点

完全背包：每种硬币可无限用
一维 dp 正序更新（完全背包）
dp[0]=0 与 INF 初始化

答案

完全背包：每种硬币数量无限，故是"完全背包"而非 0-1 背包（每硬币只能用一次）。dp[i] 表示凑出金额 i 所需最少硬币数。转移 dp[i]=min(dp[i], dp[i-coin]+1)。一维 dp 需正序更新（因为硬币可重复用，正序意味着本轮可再用同一硬币），而 0-1 背包需倒序（每物只能用一次）。边界：dp[0]=0（凑 0 元需 0 枚），其余初始化为 INF（大数，表示"暂时无法凑出"）。最终若 dp[amount] 仍为 INF 则返回 -1（无法凑出）。INF 的意义是区分"可达"与"不可达"，dp[0]=0 是递推的起点。

解析

区分背包类型看"物品是否可重复使用"：可重复→完全背包（正序），不可重复→0-1 背包（倒序）。INF 初始化是"不可达"标记，dp[0]=0 是递推锚点。这是"完全背包求最值"的经典题。

示例代码

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE / 2); // INF
    dp[0] = 0;
    for (int coin : coins)
        for (int i = coin; i <= amount; i++) // 正序：完全背包
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    return dp[amount] == Integer.MAX_VALUE / 2 ? -1 : dp[amount];
}

#

★★★

6. 打家劫舍系列（线性/环形/树形）状态设计的演进关系？

问题

说明打家劫舍系列的线性、环形、树形三题状态设计的演进关系？

考察点

线性：dp[i]=max(dp[i-1], dp[i-2]+nums[i])
环形：拆成"不取首/不取尾"两个线性
树形：树上 DP 状态（选/不选）

答案

线性（198）：dp[i] 表示前 i 家最多偷的值，转移 dp[i]=max(dp[i-1], dp[i-2]+nums[i])（不偷 i 或偷 i 则 i-1 不能偷）。环形（213）：首尾相邻，拆成两个线性问题——"偷 0..n-2（不含尾）"与"偷 1..n-1（不含首）"，取两者最大。树形（337）：树上 DP，每个节点状态分"选该节点"与"不选该节点"，选则子节点不能选，不选则子节点可选可不选，用后序遍历返回两个值。演进关系：线性是基础，环形消除首尾干扰（区间拆分），树形把线性结构推广到树结构（节点状态二选一）。三者核心都是"相邻不能同时选"的约束。

解析

该系列体现"状态设计"的演进：线性用一维 dp，环形用"取范围"拆分，树形用"节点二态"。核心约束一致（不能选相邻），只是结构维度不同。掌握线性就能迁移到环形（拆分）与树形（父子的状态约束）。

示例代码

// 线性
int rob(int[] nums) {
    int prev = 0, cur = 0;
    for (int x : nums) { int t = cur; cur = Math.max(cur, prev + x); prev = t; }
    return cur;
}
// 环形： max(rob(nums[0..n-2]), rob(nums[1..n-1]))

#

★★★

7. 编辑距离 DP 的状态转移含义如何向面试官清晰解释？

问题

解释编辑距离 DP 的状态转移含义，并将其清晰地向面试官阐述？

考察点

dp[i][j] 含义
三种操作（插入/删除/替换）的转移
边界与递推

答案

dp[i][j] 表示把 word1 的前 i 个字符变成 word2 的前 j 个字符的最少操作数。边界：dp[0][j]=j（空串变成长度 j 需 j 次插入）、dp[i][0]=i（长度 i 变空需 i 次删除）。转移：若 word1[i-1]==word2[j-1]，则 dp[i][j]=dp[i-1][j-1]（无需操作）。否则 dp[i][j]=1+min：① 替换：dp[i-1][j-1]（把 word1[i-1] 换成 word2[j-1]，两串各少一）；② 删除：dp[i-1][j]（删除 word1[i-1]，word1 少一）；③ 插入：dp[i][j-1]（在 word1 末尾插入 word2[j-1]，word2 少一）。向面试官解释：把"把 A 变成 B"翻译成"对 A 的前缀做三种操作"，每次操作都对应一个更小的子问题，取三者最小。

解析

编辑距离是"字符串 DP 的教科书"，核心是三种操作与子问题的对应：替换看两个末端都少一、删除看 A 少一、插入看 B 少一。相等时直接继承左上方。解释时用"前缀视角"（dp[i][j] 只管前 i/j 个字符）最清晰。

示例代码

int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
        else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
    }
    return dp[m][n];
}

#

★★★

8. 求有向无环图的最长路径中拓扑排序 DP 与记忆化 DFS 的等价性？

问题

求 DAG 的最长路径，说明拓扑排序 DP 与记忆化 DFS 的等价性？

考察点

DAG 保证无环，可求最长路径
拓扑排序确定 DP 顺序
记忆化 DFS 与拓扑 DP 等价

答案

DAG 最长路径（无环保证可求）。拓扑排序 DP：先拓扑排序得到线性序，按序处理每个节点，对每条边 u→v 松弛 dp[v]=max(dp[v], dp[u]+w)。因为拓扑序保证处理 u 时其所有前驱已就绪，故 dp 正确。记忆化 DFS：对每个节点递归求其最长路径长度 = max(1 + 子节点最长路径)，用 memo 缓存，避免重复计算。两者等价性：拓扑序正是"所有依赖都先被满足"的线性序，记忆化 DFS 的递归调用顺序在 DAG 上自然形成拓扑序（DFS 后序即反向拓扑序）。故两者计算同一 DP，只是执行顺序不同：拓扑 DP 显式按序，记忆化 DFS 隐式按递归。复杂度均 O(V+E)。

解析

等价性的根源是"DAG 的拓扑序 = 记忆化 DFS 的依赖顺序"。拓扑排序 DP 用显式序，记忆化 DFS 用递归栈 + 缓存，两者算的是同一个"最长路径"DP。这是"DAG 上 DP"的两种等价实现。

示例代码

// 记忆化 DFS
int[] memo;
int dfs(int u, List<List<int[]>> adj) {
    if (memo[u] != -1) return memo[u];
    int best = 0;
    for (int[] e : adj.get(u)) best = Math.max(best, e[1] + dfs(e[0], adj));
    return memo[u] = best;
}

#

★★★

9. 0/1 背包与完全背包中一维滚动数组的遍历顺序为什么相反？

问题

说明 0/1 背包与完全背包一维滚动数组的遍历顺序为何相反？

考察点

0/1 背包倒序更新
完全背包正序更新
顺序决定"是否可重复使用同一物品"

答案

0/1 背包：每件物品只能用一次，一维 dp 需倒序遍历容量（j 从大到小），因为 dp[j] 依赖 dp[j-w]，倒序保证 dp[j-w] 是"上一轮（未用当前物品）"的值，避免同一物品被重复使用。完全背包：每件物品可无限用，一维 dp 正序遍历（j 从小到大），因为 dp[j] 依赖 dp[j-w]，正序允许 dp[j-w] 已包含当前物品（即允许重复使用），正好符合完全背包语义。顺序相反的本质：倒序保证"每物品至多一次"，正序允许"每物品多次"。这是一维滚动数组下两种背包的唯一区别。

解析

遍历顺序是两种背包的"开关"：倒序=0/1（限用一次），正序=完全（可复用）。根源是"上一轮值"与"本轮值"的区分：倒序读到旧值，正序读到已更新的新值（含当前物品）。理解这一点即可正确套用任意背包题。

示例代码

// 0/1 背包：倒序
for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--) dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
// 完全背包：正序
for (int i = 0; i < n; i++)
    for (int j = w[i]; j <= W; j++) dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);

#

★★★

10. 动态规划的优化方向中滚动数组、状态压缩、单调队列与斜率优化何时用？

问题

总结动态规划的优化方向：滚动数组、状态压缩、单调队列与斜率优化各自何时使用？

考察点

滚动数组：只依赖相邻行
状态压缩：状态是子集
单调队列：转移含滑动窗口最值

答案

① 滚动数组：当 dp 只依赖前一行/前几行时，用两行或一维覆盖，把空间从 O(n²) 降到 O(n)。② 状态压缩：当状态是"子集/集合"（如 TSP、覆盖问题）时，用整数位掩码表示，dp[mask] 枚举子集，把状态空间压缩到 2^n。③ 单调队列：当转移是 dp[i]=max(dp[j])+cost 且 j 在长度受限的滑动窗口内时，用单调队列维护窗口最值，把 O(n) 取最值降到均摊 O(1)。④ 斜率优化：当转移含 dp[j] 与 j 的线性组合（dp[i]=min(dp[j]+...)，且代价关于 j 是线性函数、具备凸性）时，用凸包/单调队列维护斜率，把 O(n²) 降到 O(n)。选择依据：看状态维度与转移的结构。

解析

四种优化分别针对"空间维"、"状态编码"、"转移最值"、"转移凸性"。滚动数组最常用易、状态压缩用于子集状态、单调队列用于滑动窗口最值转移、斜率优化是竞赛级高级技巧。理解各自的适用信号（依赖、状态形态、转移形式）即可正确选型。

示例代码

// 单调队列优化：dp[i] = max(dp[j] + f(j))，j 在窗口内
// 用单调队列维护候选 j 的 dp[j]+f(j) 递减
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst(); // 过期
    dp[i] = dq.isEmpty() ? 0 : dp[dq.peekFirst()] + cost(i);
    while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast(); // 维持单调
    dq.offerLast(i);
}

#

★★★

11. 爬楼梯（LeetCode 70）中为什么 f(n)=f(n-1)+f(n-2)，与斐波那契的滚动数组优化？

问题

爬楼梯，说明为什么 f(n)=f(n-1)+f(n-2)，以及斐波那契的滚动数组优化？

考察点

递推关系 f(n)=f(n-1)+f(n-2)
与斐波那契的对应
滚动数组 O(1) 空间

答案

到达第 n 阶最后一步要么从 n-1 迈 1 阶、要么从 n-2 迈 2 阶，故 f(n)=f(n-1)+f(n-2)，边界 f(1)=1、f(2)=2。这正是斐波那契数列（移位后 f(n)=F(n+1)）。滚动数组优化：只需维护前两个值 prev2、prev1，迭代计算当前值，空间 O(1)、时间 O(n)。也可用矩阵快速幂 O(log n)（可选）。滚动数组避免存整个 O(n) 数组，因为递推只依赖前两个状态。

解析

爬楼梯是"斐波那契"的经典应用：递推关系直接来自"最后一步的选择"。滚动数组利用"只依赖前两个值"的局部性，空间降到 O(1)。这是"DP 空间优化"最基础的例子。

示例代码

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int t = a + b; a = b; b = t; }
    return b; // 滚动数组
}

#

★★★

12. 买卖股票的最佳时机（LeetCode 121/122）中一次交易维护历史最低价，多次交易用贪心累加正差价的依据？

问题

买卖股票的最佳时机：一次交易维护历史最低价，多次交易用贪心累加正差价的依据？

考察点

121 一次交易：维护历史最低价
122 多次交易：贪心累加正差价
贪心正确性：每次上涨都赚

答案

121（一次交易）：遍历时维护到当前为止的最低价格 minPrice，每天计算"若今天卖出"的利润 price-minPrice，取最大。只需一次遍历 O(n)、O(1) 空间。122（多次交易）：贪心——只要今天价格比昨天高，就假设昨天买入今天卖出，累加所有正差价。依据：多次交易可任意买卖，利润最大化等价于"把所有上涨段的差价都赚到"，因为每天可买卖一次，连续上涨可拆成逐日交易，累加正则获得总上涨量。允许当天买卖时，累加正差价是严格最优（每个上涨日贡献一份利润）。

解析

121 是"维护历史最低价"的单次最优；122 是"贪心累加正差价"，因为多段且可逐日交易，正差价之和恰为总上涨量。121 关注"一次买卖的最大差"，122 关注"所有上涨段的累加"。两者是"单次 vs 多次"的经典区分。

示例代码

// 121 一次交易
int maxProfit(int[] prices) {
    int min = Integer.MAX_VALUE, profit = 0;
    for (int p : prices) { min = Math.min(min, p); profit = Math.max(profit, p - min); }
    return profit;
}
// 122 多次交易
int maxProfit2(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
    return profit;
}

#

★★

13. 单词拆分与完全背包的映射关系？

问题

说明单词拆分与完全背包的映射关系？

考察点

把字符串看成容量、单词看成物品
完全背包：单词可重复使用
与"能否凑出"的判定

答案

单词拆分（139）：判断 s 能否由字典中的单词拼接而成。映射到完全背包：s 的长度是"容量"，字典中的每个单词是"物品"（可重复使用），dp[i] 表示 s 的前 i 个字符能否被拼出。转移：dp[i] 为真当存在 j<i 使 dp[j] 为真且 s[j..i-1] 在字典中。这是"完全背包"（物品可重复、顺序重要）的判定版本。与普通完全背包差异：物品有长度约束，且组合顺序必须匹配子串，故用"容量维度"遍历（外层是容量 i，内层枚举以 i 结尾的子串起点 j）。注意这是"排列型"完全背包（顺序重要），若外层遍历物品则无法处理顺序，故需外层容量、内层物品（或子串）。

解析

单词拆分是"完全背包的排列型"变体：单词可重复、拼接顺序重要。关键区别在遍历顺序：若外层遍历物品，只能处理"组合型"（顺序无关）；词序敏感必须外层容量、内层物品。dp 是布尔判定，体现"能否凑出"。

示例代码

boolean wordBreak(String s, List<String> dict) {
    Set<String> set = new HashSet<>(dict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++)           // 外层容量
        for (int j = 0; j < i; j++)
            if (dp[j] && set.contains(s.substring(j, i))) { dp[i] = true; break; }
    return dp[s.length()];
}

#

★★

14. 不同路径（LeetCode 62/63）中答案等于组合数 C(m+n-2, m-1)，有障碍物时如何用 DP 处理？

问题

不同路径，说明答案为何等于组合数 C(m+n-2, m-1)，以及有障碍物时如何用 DP 处理？

考察点

无障碍：路径数 = 组合数
组合数：总步数 m+n-2 中选 m-1 步向下
有障碍：DP 跳过障碍格

答案

无障碍物：从 (0,0) 到 (m-1,n-1) 只能向右或向下，共需走 m+n-2 步，其中 m-1 步向下、n-1 步向右，路径数 = 从 m+n-2 步中选 m-1 步向下的组合数 C(m+n-2, m-1)。数学上这正是"组合选择"问题。有障碍物（63）：不能用组合数，用 DP——dp[i][j] 表示到达 (i,j) 的路径数，dp[i][j]=dp[i-1][j]+dp[i][j-1]（上+左），但若 (i,j) 是障碍则 dp[i][j]=0，且边界行/列遇障碍则其后均为 0。DP 的通用性：能处理障碍、权值等组合数无法表达的约束。

解析

无障碍时组合数是"封闭解"，直接公式 O(1)；有障碍时组合数失效，DP 逐格累加，能自然处理"障碍格贡献 0"。DP 的边界初始化（首行首列）需注意障碍阻断。这是"组合数 vs DP"的对比。

示例代码

int uniquePathsWithObstacles(int[][] g) {
    int m = g.length, n = g[0].length;
    int[] dp = new int[n];
    dp[0] = g[0][0] == 0 ? 1 : 0;
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
        if (g[i][j] == 1) { dp[j] = 0; continue; }
        if (j > 0) dp[j] += dp[j - 1]; // 上+左
    }
    return dp[n - 1];
}

#

★★

15. 边权为 0/1 的最短路中为什么 0-1 BFS 用双端队列能到 O(V+E)，与普通 BFS、Dijkstra 的关系？

问题

边权为 0/1 的最短路，说明 0-1 BFS 用双端队列为何到 O(V+E)，以及与 BFS、Dijkstra 的关系？

考察点

0-1 BFS 用双端队列
0 权边入队首、1 权边入队尾
与 BFS、Dijkstra 的关系

答案

0-1 BFS：边权只有 0 或 1。用双端队列，从队首取节点，若走 0 权边则把新节点压入队首（距离不变，优先处理），若走 1 权边则压入队尾（距离+1）。这样队列中距离单调不减，每个节点至多被处理一次，复杂度 O(V+E)。原理：0 权边不增加距离，应优先扩展，双端队列保证"距离小者先出"，等价于 Dijkstra 的优先队列但用双端队列实现 O(1)。关系：普通 BFS 是边权全为 1 的特例（0-1 BFS 中无 0 权边）；Dijkstra 是任意非负权（优先队列 O(log)）；0-1 BFS 是"边权仅 0/1"时用双端队列达到 O(V+E) 的优化。

解析

0-1 BFS 是"BFS 与 Dijkstra 的中间态"：因边权只有 0/1，距离值离散，用双端队列即可维持"距离单调"的队列性质，把 Dijkstra 的 O(log) 降到 O(1)。0 权边压队首、1 权边压队尾是核心技巧。这是"特殊权值用特殊数据结构"的范例。

示例代码

// 0-1 BFS
int[] dist = new int[n];
Arrays.fill(dist, INF); dist[src] = 0;
Deque<Integer> dq = new ArrayDeque<>();
dq.offer(src);
while (!dq.isEmpty()) {
    int u = dq.poll();
    for (Edge e : adj[u]) {
        int nd = dist[u] + e.w;
        if (nd < dist[e.to]) {
            dist[e.to] = nd;
            if (e.w == 0) dq.offerFirst(e.to); // 0 权入队首
            else dq.offerLast(e.to);           // 1 权入队尾
        }
    }
}

#

★★

16. 并查集如何支持"按秩合并+路径压缩"的时间复杂度证明（反阿克曼函数）？

问题

说明并查集按秩合并+路径压缩的时间复杂度证明（反阿克曼函数）？

考察点

路径压缩与按秩合并
反阿克曼函数 α(n)
单次操作摊还 O(α(n))

答案

并查集两种优化：路径压缩（find 时把路径上节点直接指向根）与按秩合并（把秩小的根并到秩大的根下）。两者结合后，单次 find/union 的摊还复杂度为 O(α(n))，其中 α(n) 是反阿克曼函数（增长极慢，对任何实际 n 都 ≤4）。证明思路：路径压缩使树高保持极低，按秩合并使树高有界（O(log n) 无压缩时）；结合后，用"秩"定义势能，每次操作势能变化被摊还，最终以 α(n) 为界。只压缩不按秩合并：最坏情况（如链式合并导致某些 find 变深）可能退化为 O(log n) 甚至 O(n) 单次，因为不带秩约束时树可能变得很高。故两者缺一不可。

解析

O(α(n)) 是"近乎常数"的复杂度，是并查集的数据结构基石。证明依赖"秩 + 势能"的摊还分析。只压缩不按秩合并的退化提醒：秩约束防止树过高，是复杂度保证的一半。理解 α(n) 与"为什么两者都要"是关键。

示例代码

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
    return parent[x];
}
void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) parent[ra] = rb;       // 按秩合并
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
}

#

★★

17. 完全平方数（LeetCode 279）中为什么是完全背包问题，dp[n]=min(dp[n-k*k])+1 的转移？

问题

完全平方数，说明为什么是完全背包，以及 dp[n]=min(dp[n-k*k])+1 的转移？

考察点

完全背包：平方数可重复用
dp[n]=min(dp[n-k*k])+1
与零钱兑换同构

答案

完全平方数：给定 n，用最少的完全平方数（1,4,9,...）之和表示 n。这是完全背包：每个完全平方数 k² 是"物品"，可重复使用，目标是"凑出 n 且物品数最少"。转移 dp[n]=min(dp[n-k²])+1，即枚举最后一个平方数 k²，dp[n-k²] 是剩余部分的最少个数，加 1 得到当前。边界 dp[0]=0。复杂度 O(n·√n)。与零钱兑换（322）完全同构：物品是平方数，目标是最少个数。也可用 BFS 或四平方定理，但完全背包最直观。

解析

核心是"完全背包 + 最少物品数"：平方数可重复用，dp[n] 依赖所有 dp[n-k²]。这题与零钱兑换是同一模型，只是物品从"硬币"换成"平方数"。理解"完全背包求最少"即可套用。

示例代码

int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE / 2);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int k = 1; k * k <= i; k++)
            dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
    return dp[n];
}

#

★★

18. 最大正方形（LeetCode 221）中 dp[i][j]=min(上,左,左上)+1 的状态含义，为什么取三者最小？

问题

最大正方形，说明 dp[i][j]=min(上,左,左上)+1 的状态含义，以及为何取三者最小？

考察点

dp[i][j] 表示以 (i,j) 为右下角的最大正方形边长
转移取上、左、左上三者最小 +1
为什么取最小

答案

dp[i][j] 表示以 (i,j) 为右下角的最大全 1 正方形边长。若 matrix[i][j]=='1'，则 dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1。为什么取三者最小：要形成以 (i,j) 为右下角的正方形，其边长受限于三个方向——上方（dp[i-1][j] 表示向上能延伸的边长）、左方（dp[i][j-1]）、左上（dp[i-1][j-1]，对角线），三者任一不足都会限制当前正方形，故取最小值 +1。答案取所有 dp 的最大值的平方。若 matrix[i][j]=='0' 则 dp[i][j]=0。复杂度 O(n²)。

解析

"取三者最小"的直觉：以 (i,j) 为右下角的边长为 k 的正方形，要求上方、左方、左上三个 k-1 正方形都存在，缺一不可，故边长 = 三者最小 +1。这是"依赖三个邻域"的经典 DP，体现"直角约束"。

示例代码

int maximalSquare(char[][] m) {
    int rows = m.length, cols = m[0].length, max = 0;
    int[][] dp = new int[rows + 1][cols + 1];
    for (int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++)
        if (m[i - 1][j - 1] == '1') {
            dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            max = Math.max(max, dp[i][j]);
        }
    return max * max;
}

#

★★

19. 跳跃游戏（LeetCode 55/45）中维护最远可达下标判断可行性，最少步数如何用“当前边界+下一边界”贪心？

问题

跳跃游戏，说明维护最远可达下标判断可行性（55），以及最少步数用"当前边界+下一边界"贪心（45）？

考察点

55：维护最远可达下标
45：双边界贪心求最少步数
贪心正确性

答案

55（能否到达）：遍历每个位置，维护最远可达下标 furthest=max(furthest, i+nums[i])。若 i>furthest 说明无法到达 i，返回 false；遍历完则可达。O(n)、O(1)。45（最少步数）：贪心——维护当前步的右边界 curEnd 与下一段能到达的最远 rightmost。遍历时更新 rightmost=max(rightmost, i+nums[i])；当 i==curEnd 时，说明需要再跳一步，步数+1，curEnd=rightmost。这样每段贪心取"最远跳跃"，保证最少步数。正确性：贪心每次跳到当前段能到达的最远点，任何最优解不会比"每次取最远"更优（因为取最远不会减少后续可达范围）。两者都 O(n)、O(1)。

解析

55 用"最远可达"判断可行性（覆盖思想）；45 用"双边界"（当前段边界 + 下一段最远）分段计数最少步。贪心正确性基于"跳得远不劣"。45 是"贪心 + 区间覆盖"的经典应用。

示例代码

// 45 最少步数
int jump(int[] nums) {
    int jumps = 0, curEnd = 0, rightmost = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        rightmost = Math.max(rightmost, i + nums[i]);
        if (i == curEnd) { jumps++; curEnd = rightmost; } // 当前段结束，跳一次
    }
    return jumps;
}

#

★★

20. 最小路径和（LeetCode 64）中网格 DP 的边界初始化，与不同路径/最大正方形的统一视角？

问题

最小路径和，说明网格 DP 的边界初始化，以及与不同路径、最大正方形的统一视角？

考察点

网格 DP 的边界初始化（首行首列）
最小路径和转移
与不同路径/最大正方形的统一视角

答案

最小路径和：dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和，转移 dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j]。边界初始化：首行 dp[0][j]=dp[0][j-1]+grid[0][j]（只能向右），首列 dp[i][0]=dp[i-1][0]+grid[i][0]（只能向下），dp[0][0]=grid[0][0]。统一视角：不同路径（62）、最小路径和（64）、最大正方形（221）都是"左上到右下、上+左两个方向"的网格 DP，区别在于语义不同——62 求和（路径数）、64 取 min（路径和）、221 取 min+1（正方形边长）。这类题共享"首行首列初始化 + 上左转移"的框架，只是操作符不同。

解析

网格 DP 是"二维线性 DP"，统一框架是"从左/上转移 + 首行首列初始化"。不同路径数求和、最小路径和取 min、最大正方形取 min 边长，操作符变化反映语义。掌握统一框架可快速迁移。

示例代码

int minPathSum(int[][] g) {
    int m = g.length, n = g[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = g[0][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + g[0][j]; // 首行
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + g[i][0]; // 首列
    for (int i = 1; i < m; i++) for (int j = 1; j < n; j++)
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + g[i][j];
    return dp[m - 1][n - 1];
}

#

★★

21. 分割等和子集（LeetCode 416）中如何把问题转化为 0-1 背包（目标和为总和一半），与零钱兑换的区别？

问题

分割等和子集，说明如何转化为 0-1 背包（目标和为总和一半），以及与零钱兑换的区别？

考察点

转化为 0-1 背包：目标为总和一半
0-1 背包（每个数只能用一次）
与零钱兑换（完全背包）的区别

答案

分割等和子集：能否把数组分成两个和相等的子集，等价于判断"能否选出若干数使和为总和一半"。若总和为奇数直接 false。转化为 0-1 背包：每个数只能用一次，目标容量 target=sum/2，dp[i] 表示能否凑出和 i。转移 dp[i]=dp[i] || dp[i-num]（倒序 0-1 背包）。边界 dp[0]=true。与零钱兑换的区别：零钱兑换是"完全背包"（硬币可重复、求最少个数、正序），分割等和子集是"0-1 背包"（每个数只能用一次、求能否凑出、倒序）。两者背包类型、遍历方向、求值目标都不同。

解析

关键是把"均分"翻译成"选子集求和为一半"，即 0-1 背包的可行性判定。0-1 用倒序（每数一次），完全用正序（可重复）。分割等和子集是"0-1 背包可行性"的经典题，与零钱兑换（完全背包最值）形成对比。

示例代码

boolean canPartition(int[] nums) {
    int sum = 0; for (int x : nums) sum += x;
    if (sum % 2 == 1) return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int num : nums)
        for (int i = target; i >= num; i--) dp[i] = dp[i] || dp[i - num]; // 0-1 倒序
    return dp[target];
}

#

★

22. 记忆化搜索转 DP 的顺序推导中如何确定状态依赖方向（拓扑序）？

问题

说明记忆化搜索如何转 DP，以及如何确定状态依赖方向（拓扑序）？

考察点

记忆化搜索递归 + 缓存
转 DP 需确定依赖方向
按依赖逆序填表

答案

记忆化搜索：递归函数 + memo 缓存，递归时先算子状态再算当前，天然避免重复。转 DP：把递归调用换成显式状态表，关键在于确定"依赖方向"——即每个状态依赖哪些更小状态，按"被依赖方先算"的顺序填表。确定拓扑序的方法：① 分析转移方程，找出状态依赖的小状态（如 dp[i] 依赖 dp[i-1] 或 dp[i-2]）；② 按"依赖的逆序"遍历（若依赖较小下标则从小到大，若依赖较大则从大到小）；③ 区间 DP 按长度从小到大、树形 DP 用后序。若依赖关系复杂（如 DAG 有向依赖），用拓扑排序或直接保持记忆化（记忆化本身即拓扑序的一种实现）。

解析

记忆化与 DP 是同一动态规划的两种实现：记忆化用递归+缓存（隐式拓扑序），DP 用显式填表（需显式确定顺序）。确定顺序的关键是"状态依赖图"：只要保证"算每个状态时其依赖全部已算"，任何顺序都行，通常按下标单调方向或拓扑序。记忆化省去推导顺序，DP 更省栈。

示例代码

// 记忆化搜索（递归+缓存）
int fib(int n) {
    if (memo[n] != -1) return memo[n];
    if (n <= 1) return memo[n] = n;
    return memo[n] = fib(n - 1) + fib(n - 2);
}
// 转 DP：按依赖逆序（从小到大）
int fibDP(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

#

★

23. 区间 DP 与状态压缩 DP 中典型问题与转移方程设计？

问题

说明区间 DP 与状态压缩 DP 的典型问题与转移方程设计？

考察点

区间 DP：dp[i][j] 表示区间，按长度递增
状态压缩 DP：dp[mask] 表示子集
各自典型问题

答案

区间 DP：dp[i][j] 表示区间 [i,j] 的最优解，转移常为 dp[i][j]=min/max(dp[i][k]+dp[k+1][j]+cost)，按区间长度从小到大填表。典型问题：矩阵链乘、回文串分割、戳气球、合并石子。状态压缩 DP：dp[mask] 表示"已选集合为 mask"的状态，mask 是整数位掩码，转移枚举下一个加入的元素/连接，常配合位运算。典型问题：旅行商（TSP）、集合覆盖、Hamilton 路径。两者设计：区间 DP 关注"区间合并"（长度维度），状态压缩 DP 关注"子集枚举"（位掩码维度）。复杂度：区间 DP O(n³)（三重循环），状态压缩 O(n·2^n)。

解析

区间 DP 是"按长度填表"的二维 DP，关键在枚举分割点 k；状态压缩 DP 是"用位掩码表示子集"的状态设计，关键在去重与转移。两者是 DP 的两大高级范式，分别处理"区间结构"与"集合状态的组合爆炸"。

示例代码

// 区间 DP 模板（合并石子/矩阵链乘）
for (int len = 2; len <= n; len++) {          // 区间长度
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        dp[i][j] = INF;
        for (int k = i; k < j; k++)
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, j));
    }
}

#

★

24. 图的最短路径变体中带负权、多源、次短路与 A* 的适用场景？

问题

说明图的最短路径变体：带负权、多源、次短路与 A* 的适用场景？

考察点

Bellman-Ford/SPFA 处理负权
多源用虚拟源点 + 单源算法
次短路用扩展 Dijkstra

答案

带负权：Dijkstra 失效（非负权假设），用 Bellman-Ford（O(VE)，可检测负环）或 SPFA（平均更快，最坏 O(VE)）。多源：建立虚拟源点连接所有源点（边权 0），转单源最短路（Dijkstra/BFS），或跑多源 BFS。次短路：扩展 Dijkstra 的 dist 数组为"最短路 + 次短路"两个值，松弛时更新两者。A*：用启发函数 h(n)（估计到目标代价）驱动优先队列，在 admissible 启发下更快找到单源单目标最短路，适合"已知目标、启发可估"的场景（如 8 数码、寻路）。选型：负权→Bellman-Ford/SPFA；多源→虚拟源点；次短路→双值 Dijkstra；单目标+可估启发→A*。

解析

变体都围绕"基本最短路"的扩展：负权换算法、多源加虚拟源、次短路扩状态、A* 加启发。理解各自适用信号（负权、多源、需次优解、目标已知）即可正确选型。A* 在无启发时退化为 Dijkstra。

示例代码

// 次短路：dist[0] 最短路、dist[1] 次短路
int[] d0 = new int[n], d1 = new int[n];
Arrays.fill(d0, INF); Arrays.fill(d1, INF); d0[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
    int[] top = pq.poll(); int u = top[0], du = top[1];
    if (du > d1[u]) continue;
    for (Edge e : adj[u]) {
        int nd = du + e.w;
        if (nd < d0[e.to]) { d1[e.to] = d0[e.to]; d0[e.to] = nd; pq.offer(new int[]{e.to, nd}); }
        else if (nd < d1[e.to] && nd > d0[e.to]) { d1[e.to] = nd; pq.offer(new int[]{e.to, nd}); }
    }
}

#

★

25. 状态压缩 DP 中旅行商问题的状压转移与位运算优化？

问题

说明旅行商问题（TSP）的状态压缩 DP 转移与位运算优化？

考察点

dp[mask][i] 表示已访问集合 mask、当前在 i
转移枚举下一个城市
位运算优化

答案

TSP：访问所有城市后回到起点，求最短路径。状压 DP：dp[mask][i] 表示"已访问城市集合为 mask、当前位于城市 i"的最短路径。转移：dp[mask][i]=min(dp[mask^(1<<i)][j]+w[j][i])，其中 j 是 mask 中除 i 外的城市。初始化 dp[1<<0][0]=0。答案=min(dp[全集][i]+w[i][0])。位运算优化：① 用 (mask>>i)&1 判断 i 是否在集合中；② 用 mask^(1<<i) 或 mask&~(1<<i) 去掉 i；③ 枚举 mask 中未访问的 j 用 (~mask) 与预计算。复杂度 O(2^n·n²)，空间 O(2^n·n)。

解析

TSP 是状压 DP 的经典：状态是"访问集合 + 当前位置"，用位掩码表示集合。转移枚举"上一个城市 j"，用位运算快速判断集合成员与移除。状压 DP 把指数级的组合枚举压缩到 2^n 状态，是"子集状态"的标准范式。

示例代码

int tsp(int[][] w, int n) {
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, INF);
    dp[1][0] = 0; // 起点 0
    for (int mask = 1; mask < (1 << n); mask++)
        for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0)
            for (int j = 0; j < n; j++) if ((mask & (1 << j)) != 0 && j != i)
                dp[mask][i] = Math.min(dp[mask][i], dp[mask ^ (1 << i)][j] + w[j][i]);
    int ans = INF;
    for (int i = 1; i < n; i++) ans = Math.min(ans, dp[(1 << n) - 1][i] + w[i][0]);
    return ans;
}

#

★

26. 矩阵中的最长递增路径（LeetCode 329）中记忆化 DFS 的状态复用，为什么能避免重复计算？

问题

矩阵中的最长递增路径，说明记忆化 DFS 的状态复用为何能避免重复计算？

考察点

记忆化 DFS + memo 缓存
每个格子只算一次
复杂度 O(n·m)

答案

最长递增路径：对每个格子，DFS 向四个方向走值更大的格子，求最长链长。朴素 DFS 会重复计算（同一格子作为中间节点被多次访问）。记忆化：memo[i][j] 表示从 (i,j) 出发的最长递增路径长度，首次计算后缓存，再次访问直接返回。因为路径严格递增，从 (i,j) 出发的最长路径只依赖其四个更大邻居的 memo 值，与从哪条路到达 (i,j) 无关，故可复用。每个格子至多算一次，总 O(n·m)。这是"有向无环图（严格递增保证无环）上的最长路径 + 记忆化"。

解析

记忆化避免重复的关键是"子问题重叠 + 状态只需一次"：从 (i,j) 出发的最长路径是固定值，与到达方式无关，故缓存后复用。严格递增保证无环，使 DFS 可安全递归。这是"网格 DFS + 记忆化"的经典题。

示例代码

int[][] memo;
int longestIncreasingPath(int[][] m) {
    memo = new int[m.length][m[0].length];
    int best = 0;
    for (int i = 0; i < m.length; i++) for (int j = 0; j < m[0].length; j++)
        best = Math.max(best, dfs(m, i, j));
    return best;
}
int dfs(int[][] m, int i, int j) {
    if (memo[i][j] != 0) return memo[i][j];
    int best = 1;
    int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dir) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && nj >= 0 && ni < m.length && nj < m[0].length && m[ni][nj] > m[i][j])
            best = Math.max(best, 1 + dfs(m, ni, nj));
    }
    return memo[i][j] = best;
}