基础：Big O、Recursion、Backtracking 与 Dynamic Programming

在深入数据结构和算法之前，你需要掌握四个基础概念：用于衡量效率的 Big O 记法、用于将问题分解为子问题的 recursion、用于带剪枝穷举搜索的 backtracking，以及用于避免重复计算的 dynamic programming。本文从第一原理出发讲解每一个概念。

• 本章其余文件均假设你已经熟悉这四个概念。如果跳过本文，后续文件中的 \(O(n \log n)\) 标注、递归树遍历、backtracking 模板和 DP 状态转移，对你来说将如变魔术而非工程实践。

为什么是模式，而不是记忆

• LeetCode、NeetCode 和 HackerRank 上有数以千计的编程题目。没有人能全部记住，试图这样做是输家策略。面试官不会从固定题库中抽题，他们会修改、组合和伪装题目。一道记住的 "Two Sum" 解法在你见到从未做过的变体时毫无帮助。

• 好消息是：核心模式只有约 15-20 种（双指针、滑动窗口、BFS/DFS、DP、backtracking 等）。不管表面上看起来多么新颖，每道题归根结底都是这些模式中的一种，或几种的组合。面试考查的不是你是否见过这道题，而是你能否剥去表层——那些故事情节、特定数据类型和边界情况——从而识别出底层模式。

• 思考以下三道题：

  • "在 array 中找到两个数，使其和等于目标值。"
  • "找到两种分子，使其结合能之和等于某个阈值。"
  • "给定一组账户余额，找到两个账户，使其合计价值等于某笔债务。"

• 它们看起来不同，但本质上是同一道题：Two Sum。上下文（数字、分子、账户）无关紧要。结构是：在集合中搜索补数 → hash map 查找。

• 这就是为什么本章通过直觉来教模式，而不是通过重复记忆来教解法。对于每种模式，我们都会解释：

  • 哪种结构性质预示着这种模式（已排序的输入 → 双指针；子数组约束 → 滑动窗口；最优子结构 + 重叠子问题 → DP）。
  • 为什么该模式有效 —— 数学或逻辑推理，而非"它能给出正确答案"。
  • 如何适应变体 —— 通过展示简单、中等和困难变体，说明同一核心思想如何在不同上下文中应用。

• 当你深刻理解为什么滑动窗口有效（约束的单调性意味着扩展/收缩就足够了），你就可以将其应用于任何具有该结构的题目，即使是从未见过的。当你只是记住了"最长不含重复字符的子串"的代码，一旦题目改变你就束手无策。

• 实践策略：

  1. 学习模式（本章）。
  2. 练习识别伪装过的题目（每个文件末尾的 NeetCode 课后练习）。
  3. 练习在时间压力下实现。
  4. 面试中：读题 → 剥去上下文 → 识别模式 → 实现。

---

Big O 记法

• 当我们说一个算法"快"或"慢"时，需要一种精确的度量方式。Big O 记法描述算法的运行时间（或空间使用）随输入规模 \(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)\)：它们的扩展方式相同。在更快的计算机上，常数会改变，但扩展方式不会。Big O 捕获了问题的内在难度，与硬件无关。

增长率层级

• 从最快到最慢：

Big O	名称	示例	\(n = 10^6\) 时的操作次数
\(O(1)\)	常数	Array 访问、hash 查找	1
\(O(\log n)\)	对数	二分 search	20
\(O(n)\)	线性	线性扫描、单次循环	\(10^6\)
\(O(n \log n)\)	线性对数	Merge sort、高效排序	\(2 \times 10^7\)
\(O(n^2)\)	平方	嵌套循环、暴力枚举对	\(10^{12}\)（太慢）
\(O(n^3)\)	立方	三重嵌套循环、矩阵乘法	\(10^{18}\)（远太慢）
\(O(2^n)\)	指数	所有子集、暴力 backtracking	\(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}\) 次操作——太慢了。你需要更好的算法。

如何分析 Big 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 章介绍了主定理）。例如，merge sort：\(T(n) = 2T(n/2) + O(n) = O(n \log n)\)。

常见陷阱

• 隐式循环：Python 中 x in list 是 \(O(n)\)（线性扫描），但 x in set 是 \(O(1)\)。在循环内对 list 使用 in 会导致 \(O(n^2)\)，而非 \(O(n)\)。

# 差：O(n^2) —— list 上的 "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)\)——排序占主导。

• 均摊复杂度：有些操作偶尔很昂贵，但平均来说很便宜。动态 array 追加是 \(O(1)\) 均摊，因为稀少发生的 \(O(n)\) 扩容被分摊到 \(n\) 次便宜的追加操作上。不要混淆均摊 \(O(1)\) 和最坏情况 \(O(1)\)。

空间复杂度

• 空间复杂度遵循相同的 Big O 规则，应用于内存使用而非时间。

• 原地算法使用 \(O(1)\) 额外空间（不计算输入）。Quicksort 使用 \(O(\log n)\) 空间（recursion stack 深度）。Merge sort 使用 \(O(n)\)（用于合并的临时 array）。

• Recursion stack：每次递归调用都使用 stack 空间。\(n\) 层深的递归使用 \(O(n)\) 空间，即使每次调用不分配额外内存。这就是为什么在有 \(n\) 个节点的 graph 上进行递归 DFS 使用 \(O(n)\) 空间。

• 在面试中，始终说明时间和空间复杂度。\(O(n)\) 时间、\(O(n)\) 空间的解法通常可以接受，但 \(O(n)\) 时间、\(O(1)\) 空间的解法更好。面试官可能会要求你优化其中之一。

---

Recursion

• Recursion 是指 function 调用自身来解决同一问题的更小实例。对于具有递归结构的问题，这是最自然的方法：tree、嵌套结构、分治以及数学序列。

• 每个递归 function 都有两个部分：

  1. 基础情形（base case）：可以直接解决的最小实例（无需递归）。这是终止递归的条件。
  2. 递归情形（recursive case）：将问题分解为更小的子问题，递归地解决它们，然后合并结果。

示例：阶乘

def factorial(n):
    if n <= 1:        # base case
        return 1
    return n * factorial(n - 1)  # recursive case

• factorial(4) 的执行过程：

  • factorial(4) 调用 factorial(3)
  • factorial(3) 调用 factorial(2)
  • factorial(2) 调用 factorial(1)
  • factorial(1) 返回 1（base case）
  • factorial(2) 返回 2 * 1 = 2
  • factorial(3) 返回 3 * 2 = 6
  • factorial(4) 返回 4 * 6 = 24

• 每次调用都被压入 call stack。stack 持续增长直到到达 base case，然后随着每次调用的返回逐步弹出。如果递归过深（例如 Python 中的 factorial(1000000)），stack 会溢出（RecursionError）。Python 的默认递归限制是 1000。

如何递归地思考

• 关键的思维转变：相信递归。在编写递归 function 时，假设递归调用对更小的子问题返回正确答案。你只需要：

  1. 处理 base case。
  2. 将问题分解为更小的部分。
  3. 合并结果。

• 你不需要在脑海中追踪每次递归调用。这就像试图通过在心里执行每次迭代来理解循环。相反，验证："如果递归调用对更小的输入给出正确答案，我的合并步骤是否对完整输入给出正确答案？"

示例：linked list 上的 recursion

• 递归反转 linked list：

def reverse(head):
    if not head or not head.next:   # base case：0 或 1 个节点
        return head

    new_head = reverse(head.next)   # 反转剩余部分
    head.next.next = head           # 让下一个节点指回我
    head.next = None                # 我现在是尾节点
    return new_head

• 相信递归：reverse(head.next) 正确地反转了 list 的其余部分并返回新的头节点。我们只需要将当前节点附在末尾。

示例：tree 上的 recursion

• 计算二叉 tree 的高度：

def height(root):
    if not root:           # base case：空 tree 高度为 0
        return 0
    left_h = height(root.left)    # 左子树的高度
    right_h = height(root.right)  # 右子树的高度
    return 1 + max(left_h, right_h)  # 当前节点增加 1 层

• 这种模式——"递归左子树，递归右子树，合并"——解决了绝大多数 tree 问题（见文件 03）。

Recursion 与迭代

• 每个递归算法都可以转换为迭代算法（使用显式 stack 或循环）。迭代避免了 call stack 的开销和 stack 溢出的风险。

• 何时优先使用 recursion：问题具有自然的递归结构（tree、嵌套数据、分治）。递归解法更简洁、更易推理。

• 何时优先使用迭代：递归深度可能非常大（例如处理 \(10^6\) 个节点的 linked list）。迭代解法避免 stack 溢出。

• 尾递归（Tail recursion）：如果递归调用是 function 中的最后一个操作（递归调用返回后无需做任何工作），则该递归调用是"尾递归"。某些语言（Scheme、Scala）将尾调用优化为使用常数 stack 空间。Python 不优化尾调用，因此 Python 中的尾递归仍然使用 \(O(n)\) stack 空间。

常见陷阱

陷阱	示例	修复方法
缺少 base case	无限递归 → stack 溢出	始终定义何时停止
错误的 base case	递归分解中的差一错误	用最小输入（0、1、2）测试
没有缩小问题	f(n) 调用 f(n) 而非 f(n-1)	确保子问题严格更小
重复计算	Fibonacci：f(n) = f(n-1) + f(n-2) 指数级重算	使用记忆化（→ DP）
Python 递归限制	factorial(10000) 崩溃	使用 sys.setrecursionlimit 或转为迭代

---

Backtracking

• Backtracking 是一种系统性地探索所有可能解的方法：逐步构建解，当部分解不可能产生有效答案时，放弃它。

• 将其想象为在迷宫中导航。在每个路口，你选择一条路。如果你走到了死胡同，你回到最近的路口，尝试另一条路。你不从头开始——你回溯到最近的决策点。

三个步骤

每个 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. 撤销（回溯）

• 撤销步骤是 backtracking 区别于普通 recursion 的地方。没有它，state 会积累所有选择，你无法探索替代路径。

何时使用 Backtracking

• 问题要求枚举所有有效配置：所有排列、所有子集、所有有效排列（例如 N 皇后）。
• 问题要求找到任意有效配置：数独求解、迷宫路径查找。
• 搜索空间大但可以剪枝：大多数部分解可以在不完全探索的情况下提前被拒绝。

剪枝如何使其变快

• 没有剪枝的 backtracking 探索每种可能的组合——指数级时间。剪枝提前削减分支：

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 万 → 40000。好的剪枝使指数算法对中等 \(n\) 变得实用。

生成所有子集（最简单的 Backtracking）

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()
没有回溯（撤销）	state 不断增长，后续候选项看到过时的 state	在递归调用后始终执行 path.pop() 或 state.remove()
错误的循环起始点	有重复数字的子集，或排列中的不必要重用	使用 start 参数避免重访早期索引
跳过剪枝	探索明显无效的分支	在递归调用前添加 if not is_valid: continue

---

Dynamic Programming

• Dynamic programming（DP）是针对反复求解相同子问题的问题的优化技术。DP 不重复计算，而是只求解每个子问题一次并存储结果。

• DP 适用于具有两个性质的问题：

  1. 最优子结构：最优解可以由子问题的最优解构建而成。
  2. 重叠子问题：相同的子问题在递归中多次出现。

Fibonacci 的启示

• 朴素递归 Fibonacci：

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}\) 次操作——不可行。

• 使用记忆化（自顶向下 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)\) 空间。

• 使用表格法（自底向上 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. 确定 base case：哪些是可以直接求解的最小子问题？

4. 确定迭代顺序：哪些子问题必须先求解？自底向上：以确保依赖项已解决的顺序迭代。自顶向下：递归自动处理这一点。

5. 优化空间（可选）：如果 dp[i] 只依赖于前一行或前几个条目，就不需要完整的表格。

示例：思考过程

问题：给定一个正整数 array，找出非相邻元素的最大和（House Robber）。

第 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 步 —— Base case：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：状态依赖于单个索引。示例：爬楼梯、House Robber、最大子数组。

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

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

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

• 位掩码 DP：状态包含一个位掩码，表示哪些元素已被使用。示例：TSP、分配问题。状态空间为 \(O(2^n \cdot n)\)，对 \(n \leq 20\) 可行。

自顶向下 vs 自底向上

	自顶向下（记忆化）	自底向上（表格法）
实现	递归 + cache	迭代 + 表格
计算	只计算实际需要的子问题	计算所有子问题直到目标
Stack 溢出风险	有（深度递归）	无
空间优化	较难	较易（使用滚动 array）
编码难度	通常更自然（写递归，加 cache）	需要思考迭代顺序

• 在面试中，自顶向下通常更快写出。在生产环境中，自底向上通常因性能更优而更受青睐（无递归开销，更好的 cache 行为）。

常见陷阱

陷阱	示例	修复方法
错误的状态定义	dp[i] 没有捕获足够的信息来做决策	增加维度（例如用 dp[i][j] 代替 dp[i]）
缺少 base case	dp[0] 错误 → 所有后续值都错误	手动验证 base case
错误的迭代顺序	在依赖项之前计算 dp[i]	绘制依赖箭头并相应地迭代
dp 初始化不正确	当应该用无穷大时使用了 0（最小化问题）	最小化问题用 float('inf')，最大化问题用 float('-inf')
忘记考虑"跳过"选项	总是取当前元素	转移方程通常有 max(take, skip)
可变默认参数	def f(memo={}) 在调用间共享 cache	def f(memo=None): if memo is None: memo = {}
二维 DP 中的差一错误	dp 是 1-indexed 时访问 text1[i]	dp 的大小为 (m+1) x (n+1)，访问 text1[i-1]

---

综合运用

• 这四个概念形成一条递进：

  1. Big O 告诉你某个方法是否足够快。
  2. Recursion 将问题分解为子问题。
  3. Backtracking 是 recursion + 选择 + 撤销，用于穷举搜索。
  4. DP 是 recursion + 缓存，用于重叠子问题上的优化。

• 遇到新问题时：

  • 估计输入规模 \(n\)。什么 Big O 是可接受的？
  • 如果暴力法是指数级的，且问题要求枚举/找到配置：使用 backtracking（配合剪枝使其实用）。
  • 如果暴力法是指数级的，且问题要求最优值或计数，并且存在重叠子问题：使用 DP。
  • 如果问题具有将搜索空间减半的结构：使用二分 search 或分治。
  • 如果问题是关于序列且有子数组约束：使用滑动窗口或双指针。
  • 如果问题需要快速查找：使用 hash map。

• 本章其余文件将这些思想应用于特定的数据结构和模式。