02.9.1.3 DP 与回溯高频 20 题
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.9 高频题单 / 02.9.1 高频题单与解题路线
本页为索引串联型题单:每题给出一句话思路、复杂度口径、易错点与本库关联页面,完整推导见关联页面。
02.9.1.3-001 爬楼梯(LC 70)
一句话结论
dp[i] = dp[i-1] + dp[i-2],最后一步跨 1 或 2 级;滚动两个变量即可。
概念解释
考点:线性 DP;时间 O(n),空间 O(1)。
原理流程
- 状态:到第 i 阶方法数。
- 转移:最后一步两类来源。
- 初始化 dp[0]=1, dp[1]=1。
代码 / 示例
关联:DP 状态设计与转移
常见误区
- 误区:初始台阶口径混淆导致少一项。
- 误区:用递归不记忆化导致指数复杂度。
追问
- Q:每次可跨 1~m 级? A:递推改为窗口求和,可前缀和优化。
- Q:斐波那契关系? A:本题即斐波那契递推。
02.9.1.3-002 打家劫舍(LC 198)
一句话结论
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);偷当前则不能偷上一家,二选一取优。
概念解释
考点:线性状态机;时间 O(n),空间 O(1)。
原理流程
- 状态:前 i 家最大金额。
- 转移:不偷 i / 偷 i。
- 滚动两个变量。
代码 / 示例
关联:DP 状态设计与转移
常见误区
- 误区:相邻两家都偷;正解:偷 i 必须跳过 i-1。
- 误区:初始化只给 dp[0],边界 i=1 越界。
追问
- Q:环形房屋(LC 213)? A:拆成“不含首”与“不含尾”两段取 max。
- Q:树形房屋(LC 337)? A:树形 DP 选/不选两状态。
02.9.1.3-003 最大子数组和(LC 53)
一句话结论
dp[i] = max(nums[i], dp[i-1] + nums[i]);以 i 结尾的最大连续和,全局取最大。
概念解释
考点:线性 DP;时间 O(n),空间 O(1)。
原理流程
- 状态:以 i 结尾最大和。
- 转移:续前缀或从 i 重开。
- 全局记录最大值。
代码 / 示例
关联:DP 状态设计与转移
常见误区
- 误区:全负数时返回 0;正解:至少取最大单元素。
- 误区:状态定义成“前 i 个最大和”而非结尾,转移口径错误。
追问
- Q:乘积最大子数组(LC 152)? A:需同时维护最大最小乘积,负数翻转。
- Q:分治做法? A:跨中点最大和 + 左右递归。
02.9.1.3-004 零钱兑换 I(LC 322)
一句话结论
完全背包求最少件数:dp[c] = min(dp[c], dp[c-coin]+1);金额外层、硬币内层,不可达记 INF。
概念解释
考点:完全背包;时间 O(n·amount),空间 O(amount)。
原理流程
- dp 全 INF,dp[0]=0。
- 对每个金额遍历硬币转移。
- 不可达返回 -1。
代码 / 示例
关联:背包问题
常见误区
- 误区:01 背包倒序套到完全背包;正解:可重复取,金额正序。
- 误区:不可达状态参与取 min 污染结果。
追问
- Q:零钱兑换 II(LC 518)? A:求组合数,硬币外层金额内层。
- Q:贪心可行吗? A:币值非规范时不行,见 02.8.1.1-007。
02.9.1.3-005 分割等和子集(LC 416)
一句话结论
等价 01 背包:能否选出子集和为总和一半;dp[s] 表示能否凑出和 s,逐项物品更新。
概念解释
考点:01 背包判定;时间 O(n·target),空间 O(target)。
原理流程
- 总和奇数直接 false。
- 01 背包倒序更新可达和。
- dp[target] 即答案。
代码 / 示例
关联:背包问题
常见误区
- 误区:元素可重复选取;正解:每个数只用一次,倒序更新。
- 误区:总和过大未先判奇偶与上界。
追问
- Q:目标和(LC 494)? A:转化为子集和背包计数。
- Q:复杂度上限? A:target 过大时需另选模型。
02.9.1.3-006 最长递增子序列(LC 300)
一句话结论
O(n²) DP:dp[i] = max(dp[j]+1) 对 j<i 且 a[j]<a[i];O(n log n) 用 tails 数组 + 二分替换。
概念解释
考点:子序列 DP / 二分优化;时间 O(n²) 或 O(n log n),空间 O(n)。
原理流程
- DP:结尾最长长度。
- tails:各长度最小结尾值。
- 二分找首个 >= 当前值替换。
代码 / 示例
关联:子序列问题
常见误区
- 误区:tails 长度就是 LIS 长度但内容不是实际序列。
- 误区:严格递增与非严格递增二分边界不同。
追问
- Q:二维 LIS(俄罗斯套娃)? A:按一维升序一维降序再求 LIS。
- Q:最长递增子序列个数? A:DP 同时记录长度与计数。
02.9.1.3-007 最长公共子序列(LC 1143)
一句话结论
双序列 DP:dp[i][j] 为前 i、j 字符 LCS;字符相等则对角线 +1,否则取上/左较大。
概念解释
考点:双序列 DP;时间 O(mn),空间 O(mn)(可滚动 O(min))。
原理流程
- 状态:两前缀 LCS 长度。
- 相等:dp[i-1][j-1]+1。
- 不等:max(上, 左)。
代码 / 示例
关联:子序列问题
常见误区
- 误区:把公共子序列当连续子数组;正解:子序列不要求连续。
- 误区:不等时分支漏一种。
追问
- Q:最长重复子数组(LC 718)? A:连续,转移只取对角线。
- Q:输出具体 LCS? A:回溯 DP 表反向构造。
02.9.1.3-008 编辑距离(LC 72)
一句话结论
双序列 DP:相等则对角线继承,否则插入/删除/替换取三方向最小 +1;求两串变换最少操作。
概念解释
考点:字符串 DP;时间 O(mn),空间 O(mn)(可滚动)。
原理流程
- 状态:两前缀编辑距离。
- 相等:dp[i-1][j-1]。
- 不等:1 + min(左, 上, 对角)。
代码 / 示例
关联:子序列问题
常见误区
- 误区:三种操作方向对应混淆。
- 误区:空串边界未初始化。
追问
- Q:只允许删除(LC 583)? A:距离 = m+n-2·LCS。
- Q:空间优化? A:两行滚动数组。
02.9.1.3-009 买卖股票 I(LC 121)
一句话结论
一次交易:维护历史最低买入价,逐日算 当前价 - 最低价 更新最大利润。
概念解释
考点:线性贪心/DP;时间 O(n),空间 O(1)。
原理流程
- minPrice 记录历史最低。
- 每日更新利润。
- 先更最低价再算利润口径注意顺序。
代码 / 示例
关联:线性 DP 进阶
常见误区
- 误区:先卖后买时间顺序反。
- 误区:最低价当日买入当日卖口径未限制。
追问
- Q:多次交易(LC 122)? A:相邻正差累加,见 02.8.1.2-015。
- Q:最多 K 次(LC 123/188)? A:持有/未持有状态机 DP。
02.9.1.3-010 打家劫舍 III(LC 337)
一句话结论
树形 DP:后序返回 [不偷该节点, 偷该节点] 两状态;偷则子节点只能不偷,不偷则子节点取优。
概念解释
考点:树形 DP;时间 O(n),空间 O(h)。
原理流程
- 递归左右得两状态。
- 偷 = 当前值 + 左右不偷。
- 不偷 = 左右各自 max。
代码 / 示例
关联:树形 DP
常见误区
- 误区:偷父节点还累加子节点最优;正解:偷父时子必须不偷。
- 误区:返回单值丢失两状态信息。
追问
- Q:哈希记忆化递归? A:按节点存两状态,等价后序 DP。
- Q:与树形独立集关系? A:同模型,选/不选加权最大。
02.9.1.3-011 戳气球(LC 312)
一句话结论
区间 DP:dp[i][j] 为开区间 (i,j) 内戳完最大分数;枚举最后戳的 k,分数 = a[i]·a[k]·a[j] + 左右区间。
概念解释
考点:区间 DP;时间 O(n³),空间 O(n²)。
原理流程
- 两端补 1 气球。
- 按区间长度外层。
- 枚举最后戳的气球 k 合并。
代码 / 示例
关联:区间 DP
常见误区
- 误区:按先戳哪个枚举;正解:倒过来枚举最后戳的,左右区间独立。
- 误区:边界气球乘积口径错误。
追问
- Q:为什么区间 DP 适合? A:最后一步戳 k 后左右互不影响。
- Q:复杂度? A:O(n³),n 一般不大。
02.9.1.3-012 全排列 I(LC 46)
一句话结论
回溯 + used 标记:逐位从未使用元素中选,递归后撤销;无重复元素直接排列。
概念解释
考点:排列回溯;时间 O(n·n!),空间 O(n)。
原理流程
- used 标记已选。
- 空位选未用元素。
- 满长度收集,回溯撤销。
代码 / 示例
关联:排列类
常见误区
- 误区:组合用 start 而排用 used;正解:排列顺序敏感,需 used 全集判断。
- 误区:结果集未拷贝当前路径。
追问
- Q:含重复元素(LC 47)? A:排序 + 相邻同值同层跳过。
- Q:交换法排列? A:原地交换固定位置,省 used 数组。
02.9.1.3-013 组合总和(LC 39)
一句话结论
回溯 + start 控制不回头:元素可重复选取,下一层从当前下标继续;达到目标收集,超目标剪枝。
概念解释
考点:组合回溯;时间指数级,空间 O(目标深度)。
原理流程
- 排序便于剪枝。
- 从 start 起选当前及之后元素。
- 和达标收集,超限回退。
代码 / 示例
关联:组合子集类
常见误区
- 误区:可重复选取却用 i+1;正解:允许重复时下一层传 i。
- 误区:未排序导致超限剪枝失效。
追问
- Q:元素不可重复(LC 40)? A:下一层 i+1,同层去重。
- Q:组合总和 III(LC 216)? A:限制选 k 个数。
02.9.1.3-014 子集(LC 78)
一句话结论
回溯每个元素选/不选,或迭代向已有子集追加当前元素;收集所有长度组合。
概念解释
考点:子集回溯;时间 O(n·2ⁿ),空间 O(n)。
原理流程
- 路径 + start。
- 每轮收集当前路径。
- 选后续元素递归。
代码 / 示例
关联:组合子集类
常见误区
- 误区:只收集叶子;正解:每个递归节点都是合法子集。
- 误区:迭代追加时遍历旧子集快照。
追问
- Q:含重复元素子集 II(LC 90)? A:排序 + 相邻同值同层跳过。
- Q:位掩码枚举? A:见 02.8.1.3-012。
02.9.1.3-015 N 皇后(LC 51)
一句话结论
逐行回溯,列、主对角线、副对角线三类集合标记冲突;合法放置后递归下一行,收集全盘解。
概念解释
考点:棋盘回溯 + 冲突标记;时间 O(n!) 量级,空间 O(n)。
原理流程
- 每行试放列。
- 三类冲突集合判重。
- 放满 n 行记录棋盘。
代码 / 示例
关联:棋盘与 N 皇后数独
常见误区
- 误区:对角线编号只看行差;正解:主对角线 r-c、副对角线 r+c 分别编号。
- 误区:冲突标记回溯时未撤销。
追问
- Q:位掩码优化? A:用整数位表示列与对角线占用。
- Q:N 皇后 II(LC 52)? A:只计数不记录棋盘。
02.9.1.3-016 括号生成(LC 22)
一句话结论
回溯维护已用左/右括号数;左括号未满可加左,右括号少于左可加右,满 2n 收集。
概念解释
考点:合法性剪枝回溯;时间 O(卡特兰数),空间 O(n) 递归栈。
原理流程
- open < n 加左。
- close < open 加右。
- 长度 2n 收集。
代码 / 示例
关联:组合子集类
常见误区
- 误区:右括号可在左括号之前加;正解:close < open 才合法。
- 误区:左右计数口径写反。
追问
- Q:结果数量? A:第 n 个卡特兰数。
- Q:DP 做法? A:按括号对位置拆分组合。
02.9.1.3-017 单词搜索(LC 79)
一句话结论
网格回溯:从匹配首字母格子出发,四方向延伸,visited 标记,匹配失败撤销。
概念解释
考点:网格回溯;时间 O(mn·3^L),空间 O(L)。
原理流程
- 扫描起点。
- DFS 逐字符匹配。
- 越界/不匹配/已访问回退。
代码 / 示例
关联:棋盘与 N 皇后数独
常见误区
- 误区:访问标记未回溯撤销。
- 误区:首字符匹配后方向计数遗漏。
追问
- Q:多单词搜索 II(LC 212)? A:Trie 剪枝批量匹配。
- Q:能否原地改字符标记? A:临时改字符代替 visited,省空间。
02.9.1.3-018 分割回文串(LC 131)
一句话结论
回溯枚举每个切分点,子串是回文才继续;可预计算回文表加速判断。
概念解释
考点:回溯 + 回文判断;时间指数级,空间 O(n²) 预表 / O(n) 栈。
原理流程
- 从 start 枚举结束位置。
- 子串回文则加入路径递归。
- 到末尾收集方案。
代码 / 示例
关联:组合子集类
常见误区
- 误区:切分点枚举到末尾边界错误。
- 误区:回文判断重复计算可用区间 DP 预表。
追问
- Q:最少分割次数(LC 132)? A:DP 求最少切几刀。
- Q:回文判断方法? A:双指针或中心扩展,见 02.2.2.3。
02.9.1.3-019 最长回文子串(LC 5)
一句话结论
中心扩展:枚举每个中心(单字符/双字符)向两侧扩展;或区间 DP 判断回文取最长。
概念解释
考点:回文 / 区间 DP;时间 O(n²),空间 O(1)(扩展法)。
原理流程
- 枚举中心。
- 两侧相等则扩展。
- 记录最长起止。
代码 / 示例
常见误区
- 误区:只枚举单字符中心;正解:偶数长度需双字符中心。
- 误区:扩展边界越界未判断。
追问
- Q:Manacher 算法? A:O(n) 回文,面试了解概念即可。
- Q:回文子序列(LC 516)? A:不连续,区间 DP 求解。
02.9.1.3-020 正则表达式匹配(LC 10)
一句话结论
双串 DP:dp[i][j] 前 i、j 是否匹配;* 可继承前字符零次或多次,按状态转移分支处理。
概念解释
考点:复杂字符串 DP;时间 O(mn),空间 O(mn)。
原理流程
- 空模式边界初始化。
- 普通字符/
.直接匹配。 *分零次与多次转移。
代码 / 示例
关联:线性 DP 进阶
常见误区
- 误区:
*绑定前一字符的关系处理漏分支。 - 误区:空串与
a*匹配边界未初始化。
追问
- Q:通配符
*任意串(LC 44)? A:转移口径不同,贪心/DP 均可。 - Q:递归 + 记忆化? A:同状态自顶向下实现。