先看三个真实场景面试官问“求所有子集/排列/N 皇后方案”——这是回溯的专属领地DP答不上来DP只能说“有92个”说不出那92个长什么样面试官问“最少移除几个区间”“能不能跳到终点”——这是贪心的专属领地用DP能做但慢2,500倍还会被追问“为什么贪心是对的”更常见的是“这题你怎么想到用贪心的”——如果你答“感觉这样对”基本就凉了。这一周的真正目标不是“多学几道题”而是补齐两套思维工具回溯 枚举的章法 → 解决“求所有具体方案” 贪心 证明的章法 → 解决“求最优值”里的可证明子集把它们和DP放在一起你手上就有了完整的范式三件套。 回溯模板复盘三要素 一个骨架要素含义本周载体路径path已经做出的选择序列path列表 /queens[row]/ 原地改格子选择列表当前这一步还能选什么由start、used、行号、四方向界定结束条件什么时候收集答案 / 停止下探见下方“答案位置”骨架只有三步顺序不能变for 选择 in 选择列表: ← 横向本层有哪些候选for管横向 path.append(选择) ← ① 做选择 backtrack(下一层) ← ② 递归递归管纵向 path.pop() ← ③ 撤销选择回到做选择前的现场“要不要撤销”的判据这里升级为通用规则“访问过”这件事对整个问题永久成立 → 普通DFS不撤销岛屿问题只对当前路径成立 → 回溯必须撤销单词搜索。本周四题变体对照表本篇最该截图的一张表LC.78子集LC.77组合LC.46/47排列LC.51 N皇后LC.79网格解空间一维选/不选一维选k个一维排顺序二维棋盘二维网格去重手段start递增start递增used 树层去重行有序 三常数原地标记#有 start 吗✅ 有✅ 有❌ 无❌用行号❌用坐标答案位置每个节点深度k深度n深度n匹配到最后一位核心剪枝无上界剪枝树层去重列/对角线判重频次 短路返回值voidvoidvoidvoidbool复杂度O(n·2ⁿ)O(k·C(n,k))O(n·n!)O(n!)O(m·n·3ᴸ)实测锚点n20 → 104万解C(20,10) → 18.5万解n10 → 362万解n8 → 92解频次剪枝省47,000×三条最该记住的差异答案位置决定res.append写在哪一行——子集“见谁收谁”其余“到点才收”有无start决定用什么去重——有start靠顺序无start靠记忆返回值是void还是bool决定要不要“找到即短路”回溯优化手段汇总回溯代价 节点数 × 单节点代价所以优化只有两条路手段砍的是本周实例实测效果上界剪枝节点数LC.77i n-need1省43%树层去重节点数LC.47!used[i-1]省93%快115×建模降维节点数N 皇后按行放省264×预处理剪枝节点数LC.79字符频次47,000×启发式排序节点数数独MRV省81%位运算单节点代价N皇后II 掩码2.8× O(1)空间原地标记单节点代价LC.79#两次判断合并成一次一句话剪枝砍节点数位运算/原地标记砍单节点代价。 回溯 vs DP的选型判据题目问的是用什么理由求所有具体方案回溯DP把方案压成一个数丢失了形态求最优值/方案数/可行性DP只需数值无需展开方案两者都能解贪心 DP 回溯能证明无后效性就上贪心精确反例N皇后可以用DP数出“n8有92个解”但说不出这92个解分别是什么——因为DP的状态只记录“数量”方案在压缩过程中被丢弃了。只要题目要求输出方案本身回溯就是唯一通用解。从DP退化到贪心的精确条件当DP的状态可以被压缩成一个“可增量维护的标量”时DP就退化成贪心。区间调度dp[i]→lastEnd跳跃游戏dp[]→maxReach加油站n个起点候选 →tanktotal 贪心四证明手法本篇灵魂手法一交换论证① 任取一个最优解O看它的“第一个选择” ② 把O的第一个选择换成你的贪心选择得到O ③ 证明O仍然合法——关键话术“贪心选择在某个维度上不劣于原选择” ④ 证明 |O| |O| → O 也是最优解 → 贪心选择安全。第 ③ 步是心脏。MST里是“边权不大于被替换的边”加油站里是“累计油量不更少”。手法二决策包容性跳跃游戏核心找出一个标量它包容了所有历史决策的信息。跳跃游戏可达集合恒为连续前缀 [0, maxReach] → 一个整数包容了“0..i-1所有位置的跳跃能力”手法三反证 前缀和加油站两个零件引理反证从a出发在b处首次跌破0则a..b任何一站都不能作起点。定理前缀和起点 argmin(A) 1total 0是有解的充要条件。手法四拟阵理论了解层面在拟阵上求“最大权独立集”按权重降序、能加就加的贪心一定最优。问题是拟阵吗贪心结论最小生成树✅Kruskal/Prim天然正确区间调度✅按end贪心天然正确霍夫曼编码✅合并最小两堆天然正确0-1背包❌贪心没有保证贪心的正确性不是玄学它有数学根基根基的边界就是拟阵。 贪心什么时候会失败0-1背包反例经典反例背包容量W 50 物品重量, 价值A(10, 60) B(20, 100) C(30, 120) 价值密度 A 6.0 B 5.0 C 4.0 按密度贪心取 A B 160 最优解B C 220 ✅ 贪心损失 27.3%为什么失效0-1背包物品不可分割取了A后剩余20容量装不下C需30局部最优把容量切碎了反而堵死了全局最优。对比分数背包可分割用同样贪心是最优的——因为最后那点容量可以装C的2/3。“可分割”就是能否贪心的分水岭。三种贪心策略的实测失败率2万组随机对拍贪心策略失败率平均损失最坏损失按价值密度降序17.0%12.7%90.0%按价值降序8.4%18.0%63.7%按重量升序47.1%28.9%99.0%三种贪心都会失败最坏损失90%~99%。这就是为什么必须上DP。 四大贪心经典题型速查题型代表题贪心策略证明手法复杂度区间调度LC.435 / LC.452按end升序交换论证O(nlogn)分发饼干LC.455最小饼干喂最小胃口交换论证O(nlogn)跳跃覆盖LC.55 / LC.45维护覆盖范围决策包容性O(n)霍夫曼编码—合并权重最小两堆交换论证 拟阵O(nlogn)霍夫曼实测对拍字符频次霍夫曼穷举最优定长编码节省[5,9,12,13,16,45]224224✅30025.3%[3,3,3,3]2424✅240%分布越不均匀霍夫曼收益越大完全均匀时退化成定长编码。 全周总结表主题核心题目一句话收获子集与组合LC.78 LC.77子集见谁收谁组合到点才收全排列与去重LC.46 LC.47排列无start!used[i-1]表示“本层已试过”N皇后LC.51按行降维 row±col判对角线n8 →92解网格回溯LC.79 LC.37网格回溯 网格DFS 撤销频次剪枝省47,000×区间调度LC.435 LC.452按end排序正确性靠交换论证跳跃与加油站LC.55 LC.134包容性 批量排除各快2,500~3,500×硬数据回顾指标数值N皇后 n8解数92排列n10节点数9,864,101 ≈e × 10!树层去重收益省93%快 115×字符频次剪枝收益47,000×数独 MRV 收益快 15.7×区间调度 贪心 vs DP1,074×跳跃游戏 贪心 vs DP2,549×加油站 贪心 vs 暴力3,520×0-1背包 贪心失败率按密度17.0%最坏损失90%心法七求方案用回溯求最值用DP能证明无后效性才用贪心① 题目要求“输出所有方案” → 回溯 ② 题目要求“最值/方案数/可行性” → 进入 ③ ③ 能找出“可增量维护的标量”吗 能 → 贪心lastEnd / maxReach / tank 不能 → DP背包剩余容量 / LCS双串下标三个常见误用用DP做“求所有方案” → 答非所问用回溯做“求最值” → 指数级超时用“感觉”做贪心→ 答案错误且自己不知道心法八贪心不是“感觉对”是“能证明”写不出证明的贪心基本就是错的。手法核心话术适用信号交换论证“换一个不更差的选择进去解仍合法”有“第一个选择”的概念决策包容性“一个标量包容了全部历史决策”状态能压成一个数字反证/批量排除“中间站出发只会更差”候选集可成片排除拟阵“约束结构构成拟阵 → 贪心天然最优”MST、区间调度、霍夫曼面试实操写完贪心后主动补一句证明——“这里能贪心是因为结束更早留给后续空间只增不减可用交换论证严格证明”。这一句能让面试官确信你不是在蒙。八条心法合体① 先写暴力再谈优化 ② 找单调性 ③ 空间换时间 ④ DP的灵魂是状态设计 ⑤ 画表格是理解算法最快的方式 ⑥ 面试要“讲出来” ⑦ 求方案用回溯求最值用DP能证明才用贪心 ⑧ 贪心不是“感觉对”是“能证明”结语七天时间我们补齐了系列最后一块结构性空白回溯给了你枚举的章法——把解空间画成一棵树用for和递归走完用剪枝砍掉不可能的分支。贪心给了你证明的章法——十行代码背后是交换论证、包容性、批量排除三把刀。加上DP你手上有了完整的范式三件套求方案 → 回溯求最值 → DP能证明 → 贪心。最想让你带走的三句话先分类再动手。看到题面先问“这是求方案、求最值还是求可行性”范式选错努力白费贪心必须配证明。写不出证明就换DP这不是能力不足这是专业回溯的优化只有两条路——砍节点数剪枝、砍单节点代价位运算/原地标记。 今日思考题LC.322 零钱兑换凑出 amount 的最少硬币数——它该用回溯、DP还是贪心提示先看硬币面额是不是“典范的”canonical如 1/5/10/25——典范面额下贪心是对的任意面额下必须用DP。举例面额[1,3,4]、amount6贪心给4113枚最优是332枚。 
长河君 · 2026/10/10 9:12:31 · 阅读 1.2k 面试前必看！回溯与贪心总结：两大范式压实，六条心法扩充为八条
先看三个真实场景面试官问“求所有子集/排列/N 皇后方案”——这是回溯的专属领地DP答不上来DP只能说“有92个”说不出那92个长什么样面试官问“最少移除几个区间”“能不能跳到终点”——这是贪心的专属领地用DP能做但慢2,500倍还会被追问“为什么贪心是对的”更常见的是“这题你怎么想到用贪心的”——如果你答“感觉这样对”基本就凉了。这一周的真正目标不是“多学几道题”而是补齐两套思维工具回溯 枚举的章法 → 解决“求所有具体方案” 贪心 证明的章法 → 解决“求最优值”里的可证明子集把它们和DP放在一起你手上就有了完整的范式三件套。 回溯模板复盘三要素 一个骨架要素含义本周载体路径path已经做出的选择序列path列表 /queens[row]/ 原地改格子选择列表当前这一步还能选什么由start、used、行号、四方向界定结束条件什么时候收集答案 / 停止下探见下方“答案位置”骨架只有三步顺序不能变for 选择 in 选择列表: ← 横向本层有哪些候选for管横向 path.append(选择) ← ① 做选择 backtrack(下一层) ← ② 递归递归管纵向 path.pop() ← ③ 撤销选择回到做选择前的现场“要不要撤销”的判据这里升级为通用规则“访问过”这件事对整个问题永久成立 → 普通DFS不撤销岛屿问题只对当前路径成立 → 回溯必须撤销单词搜索。本周四题变体对照表本篇最该截图的一张表LC.78子集LC.77组合LC.46/47排列LC.51 N皇后LC.79网格解空间一维选/不选一维选k个一维排顺序二维棋盘二维网格去重手段start递增start递增used 树层去重行有序 三常数原地标记#有 start 吗✅ 有✅ 有❌ 无❌用行号❌用坐标答案位置每个节点深度k深度n深度n匹配到最后一位核心剪枝无上界剪枝树层去重列/对角线判重频次 短路返回值voidvoidvoidvoidbool复杂度O(n·2ⁿ)O(k·C(n,k))O(n·n!)O(n!)O(m·n·3ᴸ)实测锚点n20 → 104万解C(20,10) → 18.5万解n10 → 362万解n8 → 92解频次剪枝省47,000×三条最该记住的差异答案位置决定res.append写在哪一行——子集“见谁收谁”其余“到点才收”有无start决定用什么去重——有start靠顺序无start靠记忆返回值是void还是bool决定要不要“找到即短路”回溯优化手段汇总回溯代价 节点数 × 单节点代价所以优化只有两条路手段砍的是本周实例实测效果上界剪枝节点数LC.77i n-need1省43%树层去重节点数LC.47!used[i-1]省93%快115×建模降维节点数N 皇后按行放省264×预处理剪枝节点数LC.79字符频次47,000×启发式排序节点数数独MRV省81%位运算单节点代价N皇后II 掩码2.8× O(1)空间原地标记单节点代价LC.79#两次判断合并成一次一句话剪枝砍节点数位运算/原地标记砍单节点代价。 回溯 vs DP的选型判据题目问的是用什么理由求所有具体方案回溯DP把方案压成一个数丢失了形态求最优值/方案数/可行性DP只需数值无需展开方案两者都能解贪心 DP 回溯能证明无后效性就上贪心精确反例N皇后可以用DP数出“n8有92个解”但说不出这92个解分别是什么——因为DP的状态只记录“数量”方案在压缩过程中被丢弃了。只要题目要求输出方案本身回溯就是唯一通用解。从DP退化到贪心的精确条件当DP的状态可以被压缩成一个“可增量维护的标量”时DP就退化成贪心。区间调度dp[i]→lastEnd跳跃游戏dp[]→maxReach加油站n个起点候选 →tanktotal 贪心四证明手法本篇灵魂手法一交换论证① 任取一个最优解O看它的“第一个选择” ② 把O的第一个选择换成你的贪心选择得到O ③ 证明O仍然合法——关键话术“贪心选择在某个维度上不劣于原选择” ④ 证明 |O| |O| → O 也是最优解 → 贪心选择安全。第 ③ 步是心脏。MST里是“边权不大于被替换的边”加油站里是“累计油量不更少”。手法二决策包容性跳跃游戏核心找出一个标量它包容了所有历史决策的信息。跳跃游戏可达集合恒为连续前缀 [0, maxReach] → 一个整数包容了“0..i-1所有位置的跳跃能力”手法三反证 前缀和加油站两个零件引理反证从a出发在b处首次跌破0则a..b任何一站都不能作起点。定理前缀和起点 argmin(A) 1total 0是有解的充要条件。手法四拟阵理论了解层面在拟阵上求“最大权独立集”按权重降序、能加就加的贪心一定最优。问题是拟阵吗贪心结论最小生成树✅Kruskal/Prim天然正确区间调度✅按end贪心天然正确霍夫曼编码✅合并最小两堆天然正确0-1背包❌贪心没有保证贪心的正确性不是玄学它有数学根基根基的边界就是拟阵。 贪心什么时候会失败0-1背包反例经典反例背包容量W 50 物品重量, 价值A(10, 60) B(20, 100) C(30, 120) 价值密度 A 6.0 B 5.0 C 4.0 按密度贪心取 A B 160 最优解B C 220 ✅ 贪心损失 27.3%为什么失效0-1背包物品不可分割取了A后剩余20容量装不下C需30局部最优把容量切碎了反而堵死了全局最优。对比分数背包可分割用同样贪心是最优的——因为最后那点容量可以装C的2/3。“可分割”就是能否贪心的分水岭。三种贪心策略的实测失败率2万组随机对拍贪心策略失败率平均损失最坏损失按价值密度降序17.0%12.7%90.0%按价值降序8.4%18.0%63.7%按重量升序47.1%28.9%99.0%三种贪心都会失败最坏损失90%~99%。这就是为什么必须上DP。 四大贪心经典题型速查题型代表题贪心策略证明手法复杂度区间调度LC.435 / LC.452按end升序交换论证O(nlogn)分发饼干LC.455最小饼干喂最小胃口交换论证O(nlogn)跳跃覆盖LC.55 / LC.45维护覆盖范围决策包容性O(n)霍夫曼编码—合并权重最小两堆交换论证 拟阵O(nlogn)霍夫曼实测对拍字符频次霍夫曼穷举最优定长编码节省[5,9,12,13,16,45]224224✅30025.3%[3,3,3,3]2424✅240%分布越不均匀霍夫曼收益越大完全均匀时退化成定长编码。 全周总结表主题核心题目一句话收获子集与组合LC.78 LC.77子集见谁收谁组合到点才收全排列与去重LC.46 LC.47排列无start!used[i-1]表示“本层已试过”N皇后LC.51按行降维 row±col判对角线n8 →92解网格回溯LC.79 LC.37网格回溯 网格DFS 撤销频次剪枝省47,000×区间调度LC.435 LC.452按end排序正确性靠交换论证跳跃与加油站LC.55 LC.134包容性 批量排除各快2,500~3,500×硬数据回顾指标数值N皇后 n8解数92排列n10节点数9,864,101 ≈e × 10!树层去重收益省93%快 115×字符频次剪枝收益47,000×数独 MRV 收益快 15.7×区间调度 贪心 vs DP1,074×跳跃游戏 贪心 vs DP2,549×加油站 贪心 vs 暴力3,520×0-1背包 贪心失败率按密度17.0%最坏损失90%心法七求方案用回溯求最值用DP能证明无后效性才用贪心① 题目要求“输出所有方案” → 回溯 ② 题目要求“最值/方案数/可行性” → 进入 ③ ③ 能找出“可增量维护的标量”吗 能 → 贪心lastEnd / maxReach / tank 不能 → DP背包剩余容量 / LCS双串下标三个常见误用用DP做“求所有方案” → 答非所问用回溯做“求最值” → 指数级超时用“感觉”做贪心→ 答案错误且自己不知道心法八贪心不是“感觉对”是“能证明”写不出证明的贪心基本就是错的。手法核心话术适用信号交换论证“换一个不更差的选择进去解仍合法”有“第一个选择”的概念决策包容性“一个标量包容了全部历史决策”状态能压成一个数字反证/批量排除“中间站出发只会更差”候选集可成片排除拟阵“约束结构构成拟阵 → 贪心天然最优”MST、区间调度、霍夫曼面试实操写完贪心后主动补一句证明——“这里能贪心是因为结束更早留给后续空间只增不减可用交换论证严格证明”。这一句能让面试官确信你不是在蒙。八条心法合体① 先写暴力再谈优化 ② 找单调性 ③ 空间换时间 ④ DP的灵魂是状态设计 ⑤ 画表格是理解算法最快的方式 ⑥ 面试要“讲出来” ⑦ 求方案用回溯求最值用DP能证明才用贪心 ⑧ 贪心不是“感觉对”是“能证明”结语七天时间我们补齐了系列最后一块结构性空白回溯给了你枚举的章法——把解空间画成一棵树用for和递归走完用剪枝砍掉不可能的分支。贪心给了你证明的章法——十行代码背后是交换论证、包容性、批量排除三把刀。加上DP你手上有了完整的范式三件套求方案 → 回溯求最值 → DP能证明 → 贪心。最想让你带走的三句话先分类再动手。看到题面先问“这是求方案、求最值还是求可行性”范式选错努力白费贪心必须配证明。写不出证明就换DP这不是能力不足这是专业回溯的优化只有两条路——砍节点数剪枝、砍单节点代价位运算/原地标记。 今日思考题LC.322 零钱兑换凑出 amount 的最少硬币数——它该用回溯、DP还是贪心提示先看硬币面额是不是“典范的”canonical如 1/5/10/25——典范面额下贪心是对的任意面额下必须用DP。举例面额[1,3,4]、amount6贪心给4113枚最优是332枚。