← 课程目录 🚀 从零到一
📐 学习维度 阶段8 · 第32章 数据结构与算法专题(leetcode 分类刷题指南) 🚀 从零到一 📚 课程目录 🏠 首页 🛤️ 学习路径

32.5 动态规划与回溯:爬楼梯、股票、全排列

审校 2026-09-29 · 素材来源:raw 50 题单、raw 33 精讲复盘
📑 本篇章节导航 (共10节,点击直达)
场景:DP 与回溯的恐惧从哪来类比与定义:备忘录与决策树最小可跑示例:爬楼梯与股票原理拆解:全排列与单词搜索单词搜索:回溯的网格形态面试变体速查:一题一转移DP 审题三问与剪枝三板斧踩坑清单面试怎么问一句话总结

题单压轴四道:爬楼梯(70)、买卖股票的最佳时机(121)、全排列(46)、单词搜索(79)。前两道是动态规划(DP,把问题拆成重叠子问题并记住中间结果的解法)的入门,后两道是回溯(DFS 遍历决策树并适时撤销选择)的代表。中级岗对这两类的要求是「经典题不卡壳」——不需要征服 Hard,需要模板级熟练。

场景:DP 与回溯的恐惧从哪来

多数人对 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 从「看着发懵」到「框架落纸」不超过三分钟——DP 题的难度大半在定义状态,三问就是定义状态的脚手架。回溯的剪枝三板斧:入口剪(起点不满足直接不进)、路径剪(当前部分解已不可能达成目标,如剩余数字和不够就 return)、去重剪(同层相同值跳过,排序是前提)——剪枝写得越凶,决策树越小,面试官对「复杂度意识」的评分就越高。

踩坑清单

面试怎么问

一句话总结

DP 背「状态+转移+初始值」三件套,回溯背「选择-递归-撤销」三步舞——两类题各有一张可以画在纸上的图:便签楼梯与决策树,画出来题就解了一半。