基础：大 O、递归、回溯与动态规划

一句话总结：学 DSA 前先啃四个底层概念——大 O 度量效率、递归拆分子问题、回溯做剪枝搜索、动态规划避免重复计算，后续所有章节都建立在这上面。

🗺️ 本章导览

• 本章覆盖 DSA：基础 → 数组哈希 → 链表栈队列 → 树 → 图 → 排序搜索
• 00. 基础 (本节)：大 O、递归、回溯、动态规划
• 01. 数组与哈希：数组、字符串、哈希表
• 02. 链表、栈与队列: LinkedList、Stack、Queue、Deque
• 03. 树：二叉树、BST、堆、Trie、平衡树
• 04. 图: BFS、DFS、Dijkstra、拓扑排序
• 05. 排序与搜索：快排、归并、二分查找

在正式钻进数据结构与算法之前，你需要先掌握四个基础概念：大 O 记号衡量效率、递归把问题拆成子问题、回溯做带剪枝的穷举搜索、动态规划 (Dynamic Programming, DP) 避免重复计算。本节从第一性原理讲清每一个。

• 本章后续的文件都默认你已经吃透这四个想法。如果你跳过本节，后面文件里的 \(O(n \log n)\) 复杂度标注、递归树遍历、回溯模板、DP 状态转移都会让你觉得像变魔术，而不像工程。

为什么是模式，不是死记硬背

• LeetCode、NeetCode、HackerRank 上有几千道题。没人能全部背下来，硬试就是必输的策略。面试官不是从固定题库里抽题——他们会魔改、组合、伪装。就算你把 "Two Sum" 的解法背得滚瓜烂熟，面试官换个你没见过的变体，你还是抓瞎。

• 好消息：真正核心的模式只有 15-20 个 (双指针、滑动窗口、广度优先搜索 / 深度优先搜索 (Breadth-First Search / Depth-First Search, BFS/DFS)、DP、回溯等等)。任何题目，不管表面多新鲜，本质都归结为其中一个或几个模式的组合。面试考的不是你有没有见过这道原题，而是能不能剥掉外衣——剥掉故事、剥掉具体数据类型、剥掉边界情况，把底下的模式认出来。

• 看这三个题：

  • "在数组里找两个数，加起来等于目标值。"
  • "找两个分子，让它们的结合能加起来达到阈值。"
  • "给一组账户余额，找两个账户，它们加起来正好等于一笔欠款。"

• 看着不一样，其实是同一道题：Two Sum。上下文 (数字、分子、账户) 无关紧要。结构是：在集合中搜索补数 → 哈希表查找。

• 所以本章教的是基于直觉的模式，不是基于重复的解法。对每个模式，我们讲清楚：

  • 问题的哪种结构性质在暗示这个模式 (输入已排序 → 双指针；子数组约束 → 滑动窗口；最优子结构 + 重叠子问题 → DP)。
  • 这个模式为什么成立——数学或逻辑上的推理，而不是"反正它给出对的答案"。
  • 怎么迁移——通过简单、中等、困难三个变体，看同一个核心思想在不同上下文里怎么用。

• 当你真的搞懂为什么滑动窗口成立 (约束的单调性保证了扩张 / 收缩足够覆盖所有情况)，你就能把它用到任何有这种结构的问题上，哪怕你从来没见过。反过来，如果你只是背了 "无重复字符最长子串" 的代码，那题目稍微一变你就卡住。

• 实战策略：

  1. 学会模式 (本章)。
  2. 在伪装过的题里练识别 (每个文件末尾的 NeetCode 家庭作业)。
  3. 在时间压力下练实现。
  4. 面试时：读题 → 剥上下文 → 认模式 → 实现。

---

大 O 记号

• 当我们说一个算法"快"或"慢"时，需要一种精确的度量方式。大 O 记号 (Big O notation) 描述算法的运行时间 (或空间占用) 如何随输入规模 \(n\) 增长而变化，忽略常数因子和低阶项。

• 形式定义：\(f(n) = O(g(n))\) 意味着存在常数 \(c > 0\) 和 \(n_0\)，使得对所有 \(n \geq n_0\) 都有 \(f(n) \leq c \cdot g(n)\)。用大白话讲：当输入变大时，\(f\) 的增长速度不超过 \(g\)。

• 为什么忽略常数？因为 \(2n\) 的算法和 \(5n\) 的算法都是 \(O(n)\)——它们的增长方式一样。换台更快的电脑，常数会变，但增长趋势不变。大 O 抓的是问题内在的难度，与硬件无关。

增长率的等级

• 从最快到最慢：

大 O	名称	例子	\(n = 10^6\) 时的操作数
\(O(1)\)	常数	数组访问、哈希查找	1
\(O(\log n)\)	对数	二分查找	20
\(O(n)\)	线性	线性扫描、单层循环	\(10^6\)
\(O(n \log n)\)	线性对数	归并排序、高效排序	\(2 \times 10^7\)
\(O(n^2)\)	平方	嵌套循环、暴力配对	\(10^{12}\) (太慢)
\(O(n^3)\)	立方	三重嵌套、矩阵乘法	\(10^{18}\) (慢到没边)
\(O(2^n)\)	指数	所有子集、暴力回溯	\(10^{301030}\) (不可能)
\(O(n!)\)	阶乘	所有排列	荒谬

• 经验法则：现代电脑每秒大约执行 \(10^8\)–\(10^9\) 次简单操作。1 秒时限下：

  • \(O(n)\) 可用于 \(n \leq 10^8\)
  • \(O(n \log n)\) 可用于 \(n \leq 10^7\)
  • \(O(n^2)\) 可用于 \(n \leq 10^4\)
  • \(O(2^n)\) 可用于 \(n \leq 25\)

• 这张表能让你一眼判断出你的方案够不够快。如果 \(n = 10^5\)，你的解是 \(O(n^2)\)，那就是 \(10^{10}\) 次操作——铁定超时。你得换个更好的算法。

大 O 怎么分析

• 单层循环扫过 \(n\) 个元素：\(O(n)\)。

total = 0
for x in arr:   # n 次迭代
    total += x   # 每次 O(1)
# 总计: O(n)

• 嵌套循环：迭代次数相乘。

for i in range(n):       # n 次
    for j in range(n):   # 每次内层 n 次
        process(i, j)    # O(1)
# 总计: O(n^2)

• 每次减半的循环：\(O(\log n)\)。每次迭代把问题规模减半，所以要 \(\log_2 n\) 次迭代。

i = n
while i > 0:
    process(i)
    i //= 2
# 总计: O(log n)

• 内层依赖外层的嵌套循环：

for i in range(n):
    for j in range(i):   # j 从 0 到 i-1
        process(i, j)
# 总计: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n^2)

• 递归：写出递推关系再求解 (第 13 章讲过主定理)。比如归并排序：\(T(n) = 2T(n/2) + O(n) = O(n \log n)\)。

常见陷阱

• 隐藏循环：Python 里 x in list 是 \(O(n)\) (线性扫描)，而 x in set 是 \(O(1)\)。在循环里对列表用 in 会得到 \(O(n^2)\)，而不是 \(O(n)\)。

# 差: O(n^2) —— 对列表用 "in" 是 O(n)
for x in arr:
    if x in another_list:
        process(x)

# 好: O(n) —— 先转成 set
another_set = set(another_list)
for x in arr:
    if x in another_set:
        process(x)

• 字符串拼接：Python 里 s += c 每次都复制整个字符串。在 \(n\) 次迭代的循环里：\(O(1 + 2 + \cdots + n) = O(n^2)\)。

• 排序主导：如果你的算法先排序 (\(O(n \log n)\)) 再做线性扫描 (\(O(n)\))，总的还是 \(O(n \log n)\)——排序主导。

• 摊还复杂度 (amortised complexity)：某些操作偶尔昂贵，但平均下来便宜。动态数组的追加是摊还 \(O(1)\)，因为罕见的 \(O(n)\) 扩容被摊到 \(n\) 次便宜的追加上。别把摊还 \(O(1)\) 和最坏情况 \(O(1)\) 混为一谈。

空间复杂度

• 空间复杂度和时间一样用大 O，只不过针对内存占用。

• 原地 (in-place) 算法用 \(O(1)\) 额外空间 (不算输入)。快排是 \(O(\log n)\) 空间 (递归栈深度)。归并排序是 \(O(n)\) (归并时需要临时数组)。

• 递归栈：每次递归调用都占栈空间。\(n\) 层深的递归用 \(O(n)\) 空间，就算每次调用不额外分配内存也一样。所以在 \(n\) 个节点的图上做递归 DFS，空间是 \(O(n)\)。

• 面试时时间和空间复杂度都要说。\(O(n)\) 时间 \(O(n)\) 空间的解通常能过，但 \(O(n)\) 时间 \(O(1)\) 空间的更好。面试官可能会让你继续优化其中一个。

---

递归

• 递归 (recursion) 就是函数调用自己来解决同问题的一个更小实例。对于有递归结构的问题——树、嵌套结构、分治、数学序列——它是最自然的方式。

• 每个递归函数都有两部分：

  1. 基础情况 (base case)：最小的、能直接求解 (不用递归) 的实例。这是让递归停下来的东西。
  2. 递归情况 (recursive case)：把问题拆成更小的子问题，递归求解，再合并结果。

例子：阶乘

def factorial(n):
    if n <= 1:        # 基础情况
        return 1
    return n * factorial(n - 1)  # 递归情况

• factorial(4) 的执行过程：

  • factorial(4) 调用 factorial(3)
  • factorial(3) 调用 factorial(2)
  • factorial(2) 调用 factorial(1)
  • factorial(1) 返回 1 (基础情况)
  • factorial(2) 返回 2 * 1 = 2
  • factorial(3) 返回 3 * 2 = 6
  • factorial(4) 返回 4 * 6 = 24

• 每次调用都压入调用栈 (call stack)。栈不断增长直到触到基础情况，然后每一层返回时逐层弹出。如果递归太深 (比如 Python 里 factorial(1000000))，栈就会溢出 (RecursionError)。Python 默认递归深度上限是 1000。

怎么用递归的方式思考

• 关键的心智转换：信任递归。写递归函数时，你就假设递归调用会给出更小子问题的正确答案。你要做的只有：

  1. 处理基础情况。
  2. 把问题拆小。
  3. 合并结果。

• 你不需要在脑子里追踪每一次递归调用。那就像想通过在脑子里跑每次迭代去理解一个循环一样，费力不讨好。你只需要验证："如果递归调用对更小的输入给出了正确答案，那我的合并步骤对完整输入是否也给出正确答案？"

例子：在链表上递归

• 递归反转链表：

def reverse(head):
    if not head or not head.next:   # 基础情况: 0 个或 1 个节点
        return head

    new_head = reverse(head.next)   # 反转后面的部分
    head.next.next = head           # 让后一个节点指回自己
    head.next = None                # 现在自己变成尾
    return new_head

• 信任递归：reverse(head.next) 会正确反转剩下的链表并返回新的头。我们只要把当前节点接到末尾就行。

例子：在树上递归

• 计算二叉树的高度：

def height(root):
    if not root:           # 基础情况: 空树高度为 0
        return 0
    left_h = height(root.left)    # 左子树高度
    right_h = height(root.right)  # 右子树高度
    return 1 + max(left_h, right_h)  # 加上当前这一层

• 这个模式——"递归左边、递归右边、合并"——能解绝大多数树的题 (见文件 03)。

递归 vs 迭代

• 任何递归算法都能改写成迭代 (用显式栈或循环)。迭代避免了调用栈的开销，也没有栈溢出的风险。

• 什么时候选递归：问题本身就有天然递归结构 (树、嵌套数据、分治)。递归解更简洁，也更好推理。

• 什么时候选迭代：递归深度可能非常大 (比如处理 \(10^6\) 个节点的链表)。迭代解避免栈溢出。

• 尾递归 (tail recursion)：如果递归调用是函数的最后一个操作 (递归返回后没别的事要做)，就叫尾递归。有些语言 (Scheme、Scala) 会把尾调用优化到常量栈空间。Python 不做尾调用优化，所以 Python 里的尾递归照样吃 \(O(n)\) 栈空间。

常见坑

坑	例子	修法
缺基础情况	无限递归 → 栈溢出	一定要定义什么时候停
基础情况写错	递归拆分时差一	用最小输入 (0、1、2) 测一遍
没缩小问题	f(n) 调用 f(n) 而不是 f(n-1)	保证子问题严格更小
重复计算	斐波那契 f(n) = f(n-1) + f(n-2) 指数级重算	用记忆化 (→ DP)
Python 递归深度	factorial(10000) 崩了	用 sys.setrecursionlimit 或改成迭代

---

回溯

• 回溯 (backtracking) 是一种系统地探索所有可能解的方式：一步步构建候选解，一旦发现某个部分解不可能通向合法答案，就把它抛弃。

• 把它想象成走迷宫。每到一个岔口，你选一条路。撞到死胡同就退回上一个岔口，换另一条路走。你不是从头开始重来——你是回溯到最近的那个决策点。

三个步骤

每个回溯算法都是同一个模式：

1. 选 (choose)：挑一个候选者加进当前的部分解。
2. 探 (explore)：从这个候选者出发，递归地尝试构建完整解。
3. 撤 (unchoose)：撤销这个选择 (回溯)，试下一个候选者。

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

    for choice in choices:
        if is_valid(choice, state):
            state.add(choice)           # 1. 选
            backtrack(state, choices, result)  # 2. 探
            state.remove(choice)        # 3. 撤 (回溯)

• 撤这一步是回溯区别于普通递归的关键。不撤的话，状态会把所有选择都累加进去，你就没法探索其他分支了。

什么时候用回溯

• 问题要求枚举所有合法配置：所有排列、所有子集、所有合法排布 (比如 N 皇后)。
• 问题要求找出任意一个合法配置：解数独、找迷宫路径。
• 搜索空间很大但可以剪枝：大部分部分解可以在没完全展开前就被否决。

剪枝为什么能提速

• 不剪枝的话，回溯会枚举所有组合——指数时间。剪枝 (pruning) 提前砍掉分支：

for choice in choices:
    if not is_valid(choice, state):
        continue  # 剪枝: 跳过整个子树

    state.add(choice)
    backtrack(state, choices, result)
    state.remove(choice)

• 在 N 皇后 (文件 05) 里，放皇后前先检查列冲突和对角线冲突，把搜索树从 \(n^n\) 剪到大约 \(n!\) 个候选。对 \(n = 8\) 来说，是从 1600 万剪到 4 万。好的剪枝能让指数级算法在中等规模下也可行。

生成所有子集 (最简单的回溯)

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # 每个部分解都是一个合法子集

        for i in range(start, len(nums)):
            path.append(nums[i])        # 选
            backtrack(i + 1, path)       # 探 (i+1: 不重用)
            path.pop()                   # 撤

    backtrack(0, [])
    return result

• 对 [1, 2, 3]，递归树是：

  • [] → [1] → [1,2] → [1,2,3] (回溯) → [1,3] (回溯) → [2] → [2,3] (回溯) → [3]

• 树里每个节点都对应一次 backtrack 调用。每个叶子 (以及中间节点) 都会产出一个子集。子集总数：\(2^n\)。

生成所有排列

def permutations(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return

        for i in range(len(remaining)):
            path.append(remaining[i])                    # 选
            backtrack(path, remaining[:i] + remaining[i+1:])  # 探
            path.pop()                                   # 撤

    backtrack([], nums)
    return result

• 排列总数：\(n!\)。每个排列要 \(O(n)\) 的工作去构建 remaining，所以总的是 \(O(n \cdot n!)\)。

常见坑

坑	例子	修法
忘记复制路径	result.append(path) —— 所有条目共享同一个 list	result.append(path[:]) 或 path.copy()
忘记撤	状态一直增长，后续候选看到脏状态	递归调用后一定要 path.pop() 或 state.remove()
循环起点写错	有重复的子集，或不该重用的排列	用 start 参数避免回头访问已用过的索引
忘记剪枝	明显不合法的分支还去探索	在递归调用前加 if not is_valid: continue

---

动态规划

• 动态规划 (Dynamic Programming, DP) 是一种针对"同一个子问题被反复求解"的场景的优化技术。不再重算，DP 让每个子问题只算一次并把结果存下来。

• DP 适用于同时具备两个性质的问题：

  1. 最优子结构 (optimal substructure)：最优解可以由子问题的最优解拼出来。
  2. 重叠子问题 (overlapping subproblems)：同样的子问题在递归里反复出现。

用斐波那契看动机

• 朴素递归斐波那契：

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

• 对 fib(5)，递归树是：

  • fib(5) 调 fib(4) 和 fib(3)
  • fib(4) 调 fib(3) 和 fib(2)
  • fib(3) 被算了两次，fib(2) 被算了三次

• 这是 \(O(2^n)\)，因为每一层都分叉，而大部分分支都在重算同样的值。fib(50) 要 \(10^{15}\) 次以上的操作——完全跑不动。

• 加上记忆化 (memoisation) (自顶向下 DP)：

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

• 现在 fib(3) 只算一次、存下来，后续调用直接查表。总的：\(O(n)\) 时间，\(O(n)\) 空间。

• 换成制表 (tabulation) (自底向上 DP)：

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

• 同样 \(O(n)\) 时间，但完全不用递归，从底往上构建解。由于每个值只依赖前两个，还能进一步优化到 \(O(1)\) 空间。

DP 的通用配方

对任何 DP 问题，按以下步骤：

1. 定义状态：dp[i] (或 dp[i][j]) 代表什么？这是最难的一步。状态必须包含足够多的信息，让你能做出最优决策。

2. 写状态转移：dp[i] 怎么和更小的子问题挂钩？这就是转移方程。

3. 确定基础情况：哪些最小的子问题能直接求解？

4. 确定迭代顺序：哪些子问题必须先解？自底向上：按照能保证依赖先算出来的顺序迭代。自顶向下：递归会自动处理。

5. 优化空间 (可选)：如果 dp[i] 只依赖上一行或前几个值，那就不用存整张表。

例子：思考过程

问题：给一个正整数数组，找出不相邻元素的最大和 (打家劫舍)。

第 1 步 —— 定义状态：dp[i] = 考虑元素 nums[0..i] 时的最大和。

第 2 步 —— 写转移：对元素 \(i\)，我们要么： - 跳过：dp[i] = dp[i-1] (不选元素 \(i\) 时的最优)。 - 选它：dp[i] = dp[i-2] + nums[i] (必须跳过元素 \(i-1\)，然后加上元素 \(i\))。

所以：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

第 3 步 —— 基础情况：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。

第 4 步 —— 迭代顺序：从左到右 (每个状态依赖前两个状态)。

第 5 步 —— 空间优化：只需要保留最后两个值。

def rob(nums):
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = nums[0], max(nums[0], nums[1])

    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr

    return prev1

怎么识别 DP 题

• 问题要求最优 (最小代价、最大收益、最长序列) 或计数 (方案数)。
• 每一步都有选择 (拿 / 不拿、往左 / 往右、用这枚硬币还是不用)，整体的最优答案依赖子问题的最优答案。
• 画递归树能看到重复子问题。
• 暴力是指数级的，但不同状态的数量远小于递归调用数。

DP 的几大类

• 一维 DP：状态只有一个索引。例子：爬楼梯、打家劫舍、最大子数组。

• 二维 DP：状态有两个索引。例子：最长公共子序列 (dp[i][j] 表示字符串 1 的前 \(i\) 个字符和字符串 2 的前 \(j\) 个字符)、编辑距离、网格路径问题。

• 区间 DP：状态是一个区间 dp[i][j]，代表 arr[i..j] 上的子问题。例子：矩阵链乘、戳气球。

• 背包 DP：状态是物品索引 + 容量。例子：0/1 背包、零钱兑换、子集和。

• 状压 DP：状态里带一个位掩码，表示哪些元素被用过。例子：旅行商问题 (Travelling Salesman Problem, TSP)、指派问题。状态空间是 \(O(2^n \cdot n)\)，\(n \leq 20\) 时可行。

自顶向下 vs 自底向上

	自顶向下 (记忆化)	自底向上 (制表)
实现	递归 + 缓存	迭代 + 表
计算	只算真正用到的子问题	所有 ≤ 目标的子问题都算
栈溢出风险	有 (深度递归)	无
空间优化	难	易 (滚动数组)
编码难度	通常更自然 (写完递归加个缓存)	需要想清楚迭代顺序

• 面试时自顶向下通常写得更快。生产里通常首选自底向上，性能更好 (没有递归开销，缓存表现更好)。

常见坑

坑	例子	修法
状态定义错	dp[i] 装不下决策所需信息	加维度 (比如 dp[i][j] 代替 dp[i])
缺基础情况	dp[0] 错了 → 后面全错	手动验证基础情况
迭代顺序错	算 dp[i] 时它的依赖还没算	画出依赖箭头再按顺序迭代
dp 初始化不对	求最小时用 0 (应该用无穷大)	最小化用 float('inf')，最大化用 float('-inf')
忘了"跳过"选项	总是选当前元素	转移里通常是 max(take, skip)
可变默认参数	def f(memo={}) 会跨调用共享缓存	def f(memo=None): if memo is None: memo = {}
2D DP 差一	dp 是 1-索引却用 text1[i]	dp 用 (m+1) x (n+1)，访问 text1[i-1]

---

把它们串起来

• 这四个概念是层层递进的：

  1. 大 O 告诉你这个方案够不够快。
  2. 递归把问题拆成子问题。
  3. 回溯是递归 + 选择 + 撤销，用于穷举搜索。
  4. DP 是递归 + 缓存，用于对重叠子问题做优化。

• 拿到新题时：

  • 先估输入规模 \(n\)。什么大 O 是可以接受的？
  • 如果暴力是指数级的，问题要枚举 / 找出配置：回溯 (带剪枝让它可行)。
  • 如果暴力是指数级的，问题问最优或计数，且能看到重叠子问题：DP。
  • 如果问题有"能把搜索空间对半砍"的结构：二分查找或分治。
  • 如果问题在序列上带子数组约束：滑动窗口或双指针。
  • 如果需要快速查找：哈希表。

• 本章后续文件把这些思想应用到具体的数据结构和模式上。

---

🎯 LeetCode 题号对照 (练手清单)

• 把上面的模式落到具体题目上练手。下面列出的题号来自 LeetCode 官方题库 (题号稳定不变)，配合 NeetCode 的分类顺序，是全球公认的高频面试题集合。
• 顺序建议：简单 → 中等 → 困难。每个模式先做 1-2 道简单题内化模板，再挑中等题练变体。

递归 (Recursion)

• LC 509 Fibonacci Number (Easy)：递归模板 + 记忆化入门。
• LC 206 Reverse Linked List (Easy)：递归"信任子调用"的经典例子 (对应正文反转链表代码)。
• LC 104 Maximum Depth of Binary Tree (Easy)：树上递归三段式 (递归左 + 递归右 + 合并)。
• LC 226 Invert Binary Tree (Easy)：同上模板另一变体。

回溯 (Backtracking)

• LC 78 Subsets (Medium)：子集枚举，对应正文 subsets 代码。
• LC 46 Permutations (Medium)：全排列，对应正文 permutations 代码。
• LC 39 Combination Sum (Medium)：带剪枝的组合搜索。
• LC 22 Generate Parentheses (Medium)：约束条件下的构建。
• LC 79 Word Search (Medium)：网格上的回溯 + 撤销标记。
• LC 51 N-Queens (Hard)：正文提到的经典剪枝题。
• LC 37 Sudoku Solver (Hard)：多约束回溯的天花板。

动态规划 (Dynamic Programming)

一维 DP：

• LC 70 Climbing Stairs (Easy)：斐波那契的变形，DP 入门第一题。
• LC 198 House Robber (Medium)：对应正文 rob 代码。
• LC 53 Maximum Subarray (Medium)：Kadane 算法，一维 DP 经典。
• LC 121 Best Time to Buy and Sell Stock (Easy)：状态机 DP 入门。
• LC 300 Longest Increasing Subsequence (Medium)：一维 DP + \(O(n \log n)\) 优化。

二维 DP：

• LC 62 Unique Paths (Medium)：网格路径计数。
• LC 1143 Longest Common Subsequence (Medium)：字符串二维 DP 模板题。
• LC 72 Edit Distance (Medium)：字符串 DP 天花板 (对应正文提到的编辑距离)。

背包 DP：

• LC 322 Coin Change (Medium)：完全背包最少硬币数。
• LC 416 Partition Equal Subset Sum (Medium)：0/1 背包判定问题。

区间 DP：

• LC 312 Burst Balloons (Hard)：正文提到的经典区间 DP。

补充 (后续文件的开胃菜)

• LC 1 Two Sum (Easy)：哈希表模式 (文件 01)，也是正文开头举例的原题。
• LC 704 Binary Search (Easy)：二分查找模板 (文件 05)。
• LC 200 Number of Islands (Medium)：BFS/DFS 入门 (文件 04)。

建议节奏：每周 5-8 题，先按模式做 (同一模式连做 3-5 道)，再随机混合练识别。NeetCode 150 / Blind 75 都是基于上述题号精挑的子集，可作为路线图。

---

📌 本节要点

• 大 O 记号：描述算法随输入规模增长时的耗时或空间趋势，忽略常数因子。
• 增长率等级：从 \(O(1)\) 到 \(O(n!)\)，按 \(10^8\)-\(10^9\) 次操作 / 秒判断规模上限。
• 递归两要素：基础情况 (何时停) + 递归情况 (拆小、递归、合并)。
• 信任递归：假设递归调用对更小输入返回正确答案，只验证合并步骤。
• 回溯三步：选 (choose)、探 (explore)、撤 (unchoose)——"撤"是回溯区别于普通递归的关键。
• 剪枝：尽早否决不可能合法的分支，把指数级搜索压到可行范围。
• DP 前提：最优子结构 + 重叠子问题。
• DP 配方：定义状态、写转移、定基础情况、定迭代顺序、必要时压空间。
• 记忆化 vs 制表：自顶向下写递归 + 缓存；自底向上写迭代 + 表，性能更好。
• 模式化思维：面试里 15-20 个核心模式覆盖绝大多数题，识别结构比背题重要。