基础：大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)\)。通俗地说：对于大规模输入，\(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)  # 当前节点增加 1 层

这种模式——"递归左子树，递归右子树，合并结果"——解决了绝大多数树的问题（见文件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` 或转为迭代

回溯¶

回溯是一种系统地探索所有可能解法的方法，通过逐步构建解并在发现部分解不可能得到有效答案时立即放弃。
可以把它想象成走迷宫。在每个岔路口，你选择一条路。如果碰到死胡同，你就回到上一个岔路口尝试不同的路。你不会从头开始——你回溯到最近的一个决策点。

三个步骤¶

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

选择：选择一个候选来扩展当前的部分解。
探索：递归地尝试从这个候选构建一个完整的解。
撤销：撤销选择（回溯）并尝试下一个候选。

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 万 → 40,000。好的剪枝使指数级算法在中等规模的 \(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 问题，遵循以下步骤：

定义状态：dp[i]（或 dp[i][j]）代表什么？这是最难的一步。状态必须捕获足够的信息以做出最优决策。
写出递推关系：dp[i] 如何与更小的子问题关联？这是转移公式。
确定基本情况：哪些是最小的子问题，可以直接求解？
确定迭代顺序：哪些子问题必须先于哪些子问题求解？自底向上：按照确保依赖关系已解决的顺序迭代。自顶向下：递归会自动处理。
优化空间（可选）：如果 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] 表示字符串1的前 \(i\) 个字符和字符串2的前 \(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(take, skip)`
可变的默认参数	`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\)。什么样的 Big O 是可接受的？
- 如果暴力解法是指数级的，且问题要求枚举/寻找配置：回溯（配合剪枝使其可行）。
- 如果暴力解法是指数级的，且问题要求最优值或计数，并且你看到重叠子问题：DP。
- 如果问题具有减半搜索空间的结构：二分查找或分治法。
- 如果问题涉及序列且有子数组约束：滑动窗口或双指针。
- 如果问题需要快速查找：哈希表。