题单压轴四道:爬楼梯(70)、买卖股票的最佳时机(121)、全排列(46)、单词搜索(79)。前两道是动态规划(DP,把问题拆成重叠子问题并记住中间结果的解法)的入门,后两道是回溯(DFS 遍历决策树并适时撤销选择)的代表。中级岗对这两类的要求是「经典题不卡壳」——不需要征服 Hard,需要模板级熟练。
多数人对 DP 的恐惧来自「状态定义想不出来」。其实面试高频 DP 就三族:线性递推(爬楼梯、打家劫舍)、股票系(一次买卖、多次买卖、含冷冻期)、背包系(子集和)。每一族先背住状态含义与转移方程,见到变体做「换皮识别」。回溯则统一成一张决策树:每个节点问「这一步选什么」,走到底记录答案,回头撤销选择。
DP 像爬楼梯时每层楼都贴一张便签:「到这层有几种走法」——下次路过直接读便签,不重算。回溯像走迷宫时右手扶墙:每到一个岔路口依次尝试,走不通退回岔路口换下一条——「尝试-撤销」就是回溯名字的由来。两者的分界:DP 求「最优值/计数」,回溯求「所有具体方案」。
// 70 爬楼梯:到 i 层 = 从 i-1 迈一步 + 从 i-2 迈两步
int climbStairs(int n) {
int a = 1, b = 1; // a=f(i-2), b=f(i-1)
for (int i = 2; i <= n; i++) {
int c = a + b; // 转移方程
a = b; b = c; // 滚动变量,空间 O(1)
}
return b;
}
// 121 股票一次买卖:遍历中维护历史最低价
int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE, ans = 0;
for (int p : prices) {
min = Math.min(min, p); // 截至今天的最低买入价
ans = Math.max(ans, p - min); // 今天卖出的最优收益
}
return ans;
}
爬楼梯的本质是斐波那契——主动说「矩阵快速幂可到 O(log n)」是加分项;股票题主动指出「维护前缀最小值」的等价 DP 含义:f(i)=max(f(i-1), price(i)-min(i-1))。
全排列(46)是回溯的标准模板:路径(path)记录已选、used 数组记录用过、深度等于长度时收割:
void backtrack(int[] nums, List<Integer> path,
boolean[] used, List<List<Integer>> res) {
if (path.size() == nums.length) { // 收割条件
res.add(new ArrayList<>(path)); // 必须拷贝
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; // 做选择
path.add(nums[i]);
backtrack(nums, path, used, res);
path.remove(path.size() - 1); // 撤销选择
used[i] = false;
}
}
单词搜索(79)是回溯+网格:从每个格子起 DFS 四方向,访问过的格子临时改字符做标记,返回前恢复——「改-递归-恢复」与全排列的「选-递归-撤销」完全同构。剪枝话术:先检查首字符再进 DFS、越界与不匹配立即 return。追问预案:全排列去重(排序后同层跳过重复值)、子集与组合的 start 参数差异——这三问构成回溯的「追问三连」。
79 单词搜索(在字符网格里找词)与全排列完全同构,「改-递归-恢复」三步换成格子版:
boolean exist(char[][] g, String word) {
for (int i = 0; i < g.length; i++)
for (int j = 0; j < g[0].length; j++)
if (dfs(g, i, j, word, 0)) return true;
return false; // 每个格子都可能是起点
}
boolean dfs(char[][] g, int i, int j, String w, int k) {
if (i < 0 || i >= g.length || j < 0 || j >= g[0].length
|| g[i][j] != w.charAt(k)) return false; // 越界或不匹配
if (k == w.length() - 1) return true; // 收尾判定
g[i][j] = '#'; // 标记:改字符代替 visited
boolean ok = dfs(g, i+1, j, w, k+1) || dfs(g, i-1, j, w, k+1)
|| dfs(g, i, j+1, w, k+1) || dfs(g, i, j-1, w, k+1);
g[i][j] = w.charAt(k); // 恢复:撤销选择
return ok;
}
用改字符代替 visited 数组是空间优雅解,但必须恢复——不恢复则其他路径的格子全废。剪枝话术照旧:首字符不匹配的格子不进 DFS、k 到底立即 true。
打家劫舍:f(i)=max(f(i-1), f(i-2)+nums[i])——「不偷 vs 偷」,与爬楼梯只差一个 max。零钱兑换:完全背包,f(a)=min(f(a), f(a-coin)+1)——DP 数组下标是金额本身,这一步「把状态定义为金额」是背包族的钥匙。最长递增子序列:O(n²) 双循环起步,主动报「贪心+二分可到 O(n log n)」,与 32.6 的 lowerBound 呼应。股票系演进链:121 一次买卖 → 122 多次(贪心收集每段上坡)→ 309 含冷冻期(多一状态位)→ 188 限 k 次(二维状态)——报出演进链本身就是加分动作,展示你看到的是一族题而不是四道题。子集与组合(回溯侧):全排列用 used 数组,组合与子集改用 start 参数防重——「used 防·排列重,start 防·组合重」一句口诀收尾。
DP 的审题三问:一问求什么——最优值/计数/可行性,三者都可能是 DP,但凡要「列出所有具体方案」,回溯才是正主;二问有无后效性——当前状态定下来后,未来的转移不依赖「怎么到的」只依赖「在哪」,爬楼梯满足(只看楼层),格子带生命值的路径问题要看情况;三问状态能不能压——写完二维表主动问自己「哪些行永远只用最近两行」,爬楼梯压成两变量,背包压成一维还要讨论循环方向(倒序防重取)。三问过完,一道 DP 从「看着发懵」到「框架落纸」不超过三分钟——DP 题的难度大半在定义状态,三问就是定义状态的脚手架。回溯的剪枝三板斧:入口剪(起点不满足直接不进)、路径剪(当前部分解已不可能达成目标,如剩余数字和不够就 return)、去重剪(同层相同值跳过,排序是前提)——剪枝写得越凶,决策树越小,面试官对「复杂度意识」的评分就越高。
DP 背「状态+转移+初始值」三件套,回溯背「选择-递归-撤销」三步舞——两类题各有一张可以画在纸上的图:便签楼梯与决策树,画出来题就解了一半。