罗罗编程学习记录
本页内容 展开查看

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)。

原理流程

  1. 状态:到第 i 阶方法数。
  2. 转移:最后一步两类来源。
  3. 初始化 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)。

原理流程

  1. 状态:前 i 家最大金额。
  2. 转移:不偷 i / 偷 i。
  3. 滚动两个变量。

代码 / 示例

关联: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)。

原理流程

  1. 状态:以 i 结尾最大和。
  2. 转移:续前缀或从 i 重开。
  3. 全局记录最大值。

代码 / 示例

关联: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)。

原理流程

  1. dp 全 INF,dp[0]=0。
  2. 对每个金额遍历硬币转移。
  3. 不可达返回 -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)。

原理流程

  1. 总和奇数直接 false。
  2. 01 背包倒序更新可达和。
  3. 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)。

原理流程

  1. DP:结尾最长长度。
  2. tails:各长度最小结尾值。
  3. 二分找首个 >= 当前值替换。

代码 / 示例

关联:子序列问题

常见误区

  • 误区: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))。

原理流程

  1. 状态:两前缀 LCS 长度。
  2. 相等:dp[i-1][j-1]+1。
  3. 不等:max(上, 左)。

代码 / 示例

关联:子序列问题

常见误区

  • 误区:把公共子序列当连续子数组;正解:子序列不要求连续。
  • 误区:不等时分支漏一种。

追问

  • Q:最长重复子数组(LC 718)? A:连续,转移只取对角线。
  • Q:输出具体 LCS? A:回溯 DP 表反向构造。

02.9.1.3-008 编辑距离(LC 72)

一句话结论

双序列 DP:相等则对角线继承,否则插入/删除/替换取三方向最小 +1;求两串变换最少操作。

概念解释

考点:字符串 DP;时间 O(mn),空间 O(mn)(可滚动)。

原理流程

  1. 状态:两前缀编辑距离。
  2. 相等:dp[i-1][j-1]。
  3. 不等: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)。

原理流程

  1. minPrice 记录历史最低。
  2. 每日更新利润。
  3. 先更最低价再算利润口径注意顺序。

代码 / 示例

关联:线性 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)。

原理流程

  1. 递归左右得两状态。
  2. 偷 = 当前值 + 左右不偷。
  3. 不偷 = 左右各自 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. 两端补 1 气球。
  2. 按区间长度外层。
  3. 枚举最后戳的气球 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)。

原理流程

  1. used 标记已选。
  2. 空位选未用元素。
  3. 满长度收集,回溯撤销。

代码 / 示例

关联:排列类

常见误区

  • 误区:组合用 start 而排用 used;正解:排列顺序敏感,需 used 全集判断。
  • 误区:结果集未拷贝当前路径。

追问

  • Q:含重复元素(LC 47)? A:排序 + 相邻同值同层跳过。
  • Q:交换法排列? A:原地交换固定位置,省 used 数组。

02.9.1.3-013 组合总和(LC 39)

一句话结论

回溯 + start 控制不回头:元素可重复选取,下一层从当前下标继续;达到目标收集,超目标剪枝。

概念解释

考点:组合回溯;时间指数级,空间 O(目标深度)。

原理流程

  1. 排序便于剪枝。
  2. 从 start 起选当前及之后元素。
  3. 和达标收集,超限回退。

代码 / 示例

关联:组合子集类

常见误区

  • 误区:可重复选取却用 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)。

原理流程

  1. 路径 + start。
  2. 每轮收集当前路径。
  3. 选后续元素递归。

代码 / 示例

关联:组合子集类

常见误区

  • 误区:只收集叶子;正解:每个递归节点都是合法子集。
  • 误区:迭代追加时遍历旧子集快照。

追问

  • Q:含重复元素子集 II(LC 90)? A:排序 + 相邻同值同层跳过。
  • Q:位掩码枚举? A:见 02.8.1.3-012。

02.9.1.3-015 N 皇后(LC 51)

一句话结论

逐行回溯,列、主对角线、副对角线三类集合标记冲突;合法放置后递归下一行,收集全盘解。

概念解释

考点:棋盘回溯 + 冲突标记;时间 O(n!) 量级,空间 O(n)。

原理流程

  1. 每行试放列。
  2. 三类冲突集合判重。
  3. 放满 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) 递归栈。

原理流程

  1. open < n 加左。
  2. close < open 加右。
  3. 长度 2n 收集。

代码 / 示例

关联:组合子集类

常见误区

  • 误区:右括号可在左括号之前加;正解:close < open 才合法。
  • 误区:左右计数口径写反。

追问

  • Q:结果数量? A:第 n 个卡特兰数。
  • Q:DP 做法? A:按括号对位置拆分组合。

02.9.1.3-017 单词搜索(LC 79)

一句话结论

网格回溯:从匹配首字母格子出发,四方向延伸,visited 标记,匹配失败撤销。

概念解释

考点:网格回溯;时间 O(mn·3^L),空间 O(L)。

原理流程

  1. 扫描起点。
  2. DFS 逐字符匹配。
  3. 越界/不匹配/已访问回退。

代码 / 示例

关联:棋盘与 N 皇后数独

常见误区

  • 误区:访问标记未回溯撤销。
  • 误区:首字符匹配后方向计数遗漏。

追问

  • Q:多单词搜索 II(LC 212)? A:Trie 剪枝批量匹配。
  • Q:能否原地改字符标记? A:临时改字符代替 visited,省空间。

02.9.1.3-018 分割回文串(LC 131)

一句话结论

回溯枚举每个切分点,子串是回文才继续;可预计算回文表加速判断。

概念解释

考点:回溯 + 回文判断;时间指数级,空间 O(n²) 预表 / O(n) 栈。

原理流程

  1. 从 start 枚举结束位置。
  2. 子串回文则加入路径递归。
  3. 到末尾收集方案。

代码 / 示例

关联:组合子集类

常见误区

  • 误区:切分点枚举到末尾边界错误。
  • 误区:回文判断重复计算可用区间 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)(扩展法)。

原理流程

  1. 枚举中心。
  2. 两侧相等则扩展。
  3. 记录最长起止。

代码 / 示例

关联:区间 DP、字符串匹配 KMP/RK 与回文

常见误区

  • 误区:只枚举单字符中心;正解:偶数长度需双字符中心。
  • 误区:扩展边界越界未判断。

追问

  • 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)。

原理流程

  1. 空模式边界初始化。
  2. 普通字符/. 直接匹配。
  3. * 分零次与多次转移。

代码 / 示例

关联:线性 DP 进阶

常见误区

  • 误区:* 绑定前一字符的关系处理漏分支。
  • 误区:空串与 a* 匹配边界未初始化。

追问

  • Q:通配符 * 任意串(LC 44)? A:转移口径不同,贪心/DP 均可。
  • Q:递归 + 记忆化? A:同状态自顶向下实现。