算法题分类：从题目特征到解题模型

LOCAL NOTE · REWRITTEN & SANITIZED

刷题最难的部分通常不是把模板敲出来，而是判断题目属于什么模型。分类的目标也不是给每道题贴唯一标签，而是快速发现它利用了哪种结构：连续性、单调性、重复状态、局部最优或图上的连通关系。

四个诊断问题

读完题目后，我会先问四件事：

1. 搜索空间是什么：数组区间、树、图、排列组合，还是状态序列？
2. 目标是什么：存在性、计数、最值、路径，还是枚举全部方案？
3. 有没有可利用结构：有序、单调、连续、局部依赖或重叠子问题？
4. 状态如何变化：加入一个元素能否增量更新，选择一次后能否撤销？

flowchart TD
  A[读取题目] --> B{连续子数组或子串}
  B -->|是| C[滑动窗口 / 前缀和]
  B -->|否| D{判定函数单调}
  D -->|是| E[二分答案]
  D -->|否| F{需要枚举所有方案}
  F -->|是| G[回溯 + 剪枝]
  F -->|否| H{存在重叠子问题}
  H -->|是| I[动态规划]
  H -->|否| J{节点与边关系}
  J -->|是| K[BFS / DFS / 最短路]
  J -->|否| L[哈希 / 堆 / 栈 / 贪心]

题目特征速查

题目中的信号	优先想到	核心问题
判断元素是否出现、频次统计	哈希表	键和值分别表示什么
连续区间和、多次区间查询	前缀和	是否需要一维或二维前缀
最长或最短连续子串	滑动窗口	何时扩张、收缩、更新答案
第一个或最后一个满足条件的位置	二分查找	判定函数是否单调
Top-K、动态最值	堆	维护大顶堆还是小顶堆
左右第一个更大或更小元素	单调栈	栈内保持递增还是递减
无权图最少步数	BFS	状态去重和层数如何记录
枚举组合、排列、切割方案	回溯	路径、选择列表、结束条件
最值且存在重复子问题	动态规划	状态、选择、转移方程
区间合并或覆盖	排序 + 贪心	按起点还是终点排序

递归的三种面貌

递归只是一种实现形式，背后至少有三种不同思维。

遍历

遍历把递归函数看作进入每个节点的过程，通常通过外部变量收集结果。树的 DFS、图遍历和部分回溯属于这一类。

分解问题

分解问题要求先得到子问题的返回值，再合成当前问题。例如二叉树最大深度：当前深度等于左右子树最大深度加一。归并排序和树形 DP 也属于这条路线。

枚举决策树

回溯是在决策树上进行 DFS。每个节点包含三项：已经选择的路径、剩余选择列表、结束条件。

def backtrack(path, choices):
    if is_complete(path):
        result.append(path.copy())
        return

    for choice in choices:
        if should_prune(path, choice):
            continue
        apply(path, choice)
        backtrack(path, next_choices(choices, choice))
        undo(path, choice)

“做选择、递归、撤销选择”必须对称。剪枝一般放在递归调用前，因为目标就是避免进入不可能产生答案的子树。

回溯与动态规划的分界

两者都可能来自暴力穷举，但优化方式不同：

• 回溯关注枚举不同决策路径，通常需要全部方案或约束下的可行方案；
• 动态规划关注多个路径是否到达同一状态，通过记忆化避免重复计算；
• 若问题要求列出所有排列，重复状态通常不能直接合并；
• 若问题只求最值或计数，并且未来只依赖有限状态，往往可以设计 DP。

动态规划可以按以下顺序建模：

1. 定义 dp 状态及其语义；
2. 枚举当前状态允许的选择；
3. 写出状态转移；
4. 根据状态定义确定 base case；
5. 确定遍历顺序，保证依赖状态已计算；
6. 用小样例手推数组，检查边界和非法状态。

数据结构不是题型，维护目标才是

同一道题可能出现多种数据结构，关键是它们维护了什么不变量：

• 哈希表维护“是否出现”或“出现次数”；
• 堆维护动态集合中的极值；
• 单调栈维护尚未找到答案的一组候选元素；
• 并查集维护动态连通分量；
• Trie 维护字符串前缀；
• 双端队列可以维护滑动窗口中的单调候选集。

因此看到“使用堆”并不算分析完成，还要说明堆顶代表什么、元素何时入堆和出堆，以及堆的大小是否有界。

建立自己的错题索引

相比按题号记录，我更倾向于按“错误原因”归档：

• 没识别出单调性；
• 搜索区间定义前后不一致；
• 状态定义缺少一个维度；
• 回溯没有正确撤销状态；
• BFS 忘记在入队时去重；
• 贪心选择缺少交换论证；
• 只记住模板，没有证明使用条件。

这样复习时看到的不是几十份互不相关的答案，而是一组会反复出现的思维缺口。后续专题会继续拆分图论、动态规划、回溯和单调数据结构。