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

在深入学习数据结构和算法之前，你需要掌握四个基本概念：用于衡量效率的大O记号、将问题分解为子问题的递归、通过剪枝进行穷举搜索的回溯，以及避免重复计算的动态规划。本篇将从基本原理出发讲解这些内容。

• 本章后续的文件默认你已熟悉这四个概念。如果你跳过本篇，那么后面文件中的 \(O(n \log n)\) 复杂度标注、递归树遍历、回溯模板以及DP状态转移，在你看来就会像魔法而非工程学。

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

• LeetCode、NeetCode、HackerRank 上有成千上万道编程题。没有人能全部记住，试图这样做是徒劳的。面试官不会从固定题库里选题，他们会修改、组合、变换题目。一个死记硬背的“两数之和”解法，在你遇到一个从未见过的变体时毫无帮助。

• 好消息是：核心模式只有大约 15-20 种（双指针、滑动窗口、BFS/DFS、DP、回溯等）。任何问题，无论表面看起来多么新颖，都可以归结为这些模式中的一个或几个的组合。面试考察的不是你是否见过这个具体问题，而是你是否能够剥去问题的背景、故事、具体数据类型和边界情况，识别出底层的模式。

• 考虑这三个问题：

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

• 它们看起来不同，但其实是同一个问题：两数之和。背景（数字、分子、账户）无关紧要。结构是：在一个集合中搜索补数 → 哈希表查找。

• 这就是本章通过直觉而非重复练习来教授模式的原因。对于每种模式，我们会解释：

  • 问题的什么结构特征提示了该模式（已排序 → 双指针；子数组约束 → 滑动窗口；最优子结构 + 重叠子问题 → DP）。
  • 为什么该模式有效——数学或逻辑推理，而不只是“它能给出正确答案”。
  • 如何调整它——通过展示简单、中等、困难的不同变体，其中相同的核心思想适用于不同场景。

• 当你深刻理解了为什么滑动窗口有效（约束的单调性使得扩展/收缩就足够了），你可以将其应用于任何具有该结构的问题，即使是没见过的。如果你只背下了“无重复字符的最长子串”的代码，一旦问题发生变化，你就卡住了。

• 实用的策略：

  1. 学习模式（本章）。
  2. 练习识别模式——在伪装的问题中识别（每个文件末尾的 NeetCode 练习题）。
  3. 限时练习实现。
  4. 面试中：读题 → 剥离背景 → 识别模式 → 实现。

---

大O记号

• 当我们说一个算法“快”或“慢”时，需要精确的度量方式。大O记号描述了算法的运行时间（或空间使用）随着输入规模 \(n\) 增长而增长的速度，忽略常数因子和低阶项。

• 形式化定义：\(f(n) = O(g(n))\) 意味着存在常数 \(c > 0\) 和 \(n_0\)，使得对于所有 \(n \geq n_0\)，有 \(f(n) \leq c \cdot g(n)\)。通俗地说：当 \(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)\)——排序占主导。

• 摊还复杂度：某些操作偶尔昂贵但平均便宜。动态数组的追加操作是摊还 \(O(1)\)，因为罕见的 \(O(n)\) 扩容代价被摊分到 \(n\) 次廉价追加中。不要把摊还 \(O(1)\) 与最坏情况 \(O(1)\) 混淆。

空间复杂度

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

• 原地算法使用 \(O(1)\) 额外空间（不计输入）。快速排序是 \(O(\log n)\) 空间（递归栈深度）。归并排序是 \(O(n)\)（用于合并的临时数组）。

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

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

---

递归

• 递归是指一个函数调用自身来解决同一问题的更小实例。它是处理具有递归结构的问题的最自然方式：树、嵌套结构、分治法、数学序列等。

• 每个递归函数包含两个部分：

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

示例：阶乘

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

• 每次调用被压入调用栈。栈不断增长直到达到基本情况，然后在每次返回时展开。如果递归太深（例如 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\) 个节点的链表）。迭代解法避免了栈溢出。

• 尾递归：如果递归调用是函数的最后一个操作（递归调用返回后没有其他工作），则该递归调用是“尾递归”的。某些语言（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 或转换为迭代

---

回溯

• 回溯是一种系统性地探索所有可能解的方法，通过逐步构建解，并放弃那些不可能导致有效答案的部分解。

• 可以想象成在迷宫中导航。在每个岔路口，你选择一条路径。如果遇到死胡同，你就回到上一个岔路口尝试另一条路径。你不是从头开始——你回溯到最近的决策点。

三个步骤

每个回溯算法都遵循相同的模式：

1. 选择：选出一个候选来扩展当前的部分解。
2. 探索：递归地尝试从这个候选构建完整解。
3. 撤销选择：撤销刚才的选择（回溯），然后尝试下一个候选。

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 皇后）。
• 问题要求找到任意一个有效配置：数独求解、迷宫寻路。
• 搜索空间很大但可以剪枝：大多数部分解可以在不完全探索的情况下提前被拒绝。

剪枝如何让它变快

• 没有剪枝时，回溯会探索每一种可能的组合——指数级时间。剪枝可以提前切断分支：

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 万。良好的剪枝使得指数级算法在中等规模的 \(n\) 下变得可行。

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

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) — 所有条目共享同一列表	result.append(path[:]) 或 path.copy()
没有撤销选择	状态持续增长，后续候选看到过时状态	总是在递归调用后 path.pop() 或 state.remove()
循环起始索引错误	子集出现重复，或排列中出现不想要的重复使用	使用 start 参数避免回头访问之前的索引
忽略剪枝	探索明显无效的分支	在递归调用前加入 if not is_valid: continue

---

动态规划

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

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

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

斐波那契数列的启示

• 朴素递归斐波那契：

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. 确定基本情况：哪些是最小的、可以直接求解的子问题？

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 的分类

• 1D DP：状态依赖于单个索引。示例：爬楼梯、打家劫舍、最大子数组和。

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

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

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

• 状态压缩 DP：状态包含一个位掩码，表示哪些元素已被使用。示例：旅行商问题、分配问题。状态空间为 \(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(取, 不取)
可变默认参数	def f(memo={}) 会在调用间共享缓存	def f(memo=None): if memo is None: memo = {}
2D DP 中的差一错误	当 dp 是 1-indexed 时访问 text1[i]	dp 大小为 (m+1) x (n+1)，访问 text1[i-1]

---

融会贯通

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

  1. 大O 告诉你一个方法是否足够快。
  2. 递归 将问题分解为子问题。
  3. 回溯 = 递归 + 选择 + 撤销，用于穷举搜索。
  4. DP = 递归 + 缓存，用于重叠子问题上的优化。

• 遇到新问题时：

  • 估算输入规模 \(n\)。可接受的大O是什么？
  • 如果暴力解是指数级，且问题要求枚举/寻找配置：回溯（配合剪枝使其可行）。
  • 如果暴力解是指数级，且问题要求最优化或计数，并且你看到重叠子问题：DP。
  • 如果问题具有将搜索空间减半的结构：二分查找或分治法。
  • 如果问题是关于序列且带有子数组约束：滑动窗口或双指针。
  • 如果问题需要快速查找：哈希表。

• 本章剩余的文件将把这些概念应用到具体的数据结构和模式中。