第9章：动态规划的本质

动态规划（Dynamic Programming，DP）可能是算法题中最让人又爱又恨的主题。爱它，是因为一旦掌握，许多看似复杂的问题都能迎刃而解；恨它，是因为初学时总感觉"知道是DP，但就是想不出状态"。本章将从函数式编程的视角重新审视DP，把它理解为"带缓存的递归"，这样能让DP的本质更加清晰。

对于有函数式编程背景的工程师来说，DP其实就是将纯函数的递归调用结果缓存起来。当我们用代数的眼光看待状态转移，会发现DP本质上是在求解一个递推关系式。这种理解方式不仅更加自然，还能帮助我们系统地设计状态和转移方程。

大纲

9.1 重叠子问题与最优子结构

  • 动态规划的两个核心特征
  • 从递归树看重叠子问题
  • 最优子结构的数学表达
  • 例题：不同的二叉搜索树

9.2 状态定义的艺术

  • 状态是什么：问题的阶段性描述
  • 好的状态定义标准
  • 从暴力搜索到状态抽象
  • 例题：打家劫舍系列

9.3 递推vs递归：两种实现方式

  • 自顶向下：记忆化搜索
  • 自底向上：表格填充
  • 两种方式的优劣对比
  • 例题：不同路径系列

9.4 空间优化：滚动数组与状态压缩

  • 观察状态依赖关系
  • 滚动数组技巧
  • 状态压缩的时机
  • 例题：股票买卖系列

9.1 重叠子问题与最优子结构

动态规划的两个核心特征

动态规划能够解决的问题必须同时满足两个条件：重叠子问题和最优子结构。这两个概念听起来抽象，但用函数式编程的视角来看就很自然了。

重叠子问题意味着递归过程中会多次计算相同的子问题。想象一下计算斐波那契数列 $F(n) = F(n-1) + F(n-2)$，如果直接递归，$F(n-1)$ 和 $F(n-2)$ 都会计算 $F(n-3)$，这就是重叠。从函数调用的角度看，相同的参数会被调用多次，这正是需要缓存（memoization）的信号。

最优子结构则是说，大问题的最优解包含子问题的最优解。用代数语言描述：如果 $OPT(n)$ 表示规模为 $n$ 的问题的最优解，那么 $OPT(n)$ 可以通过某种方式由 $OPT(k)$（其中 $k < n$）构造出来。这保证了我们可以自底向上地构建解。

从递归树看重叠子问题

让我们通过 LeetCode 96 题"不同的二叉搜索树"来具体理解这两个概念。问题是：给定整数 n，求由 1 到 n 构成的不同二叉搜索树的个数。

首先用纯递归思考：

  • 选择 i 作为根节点（$1 \leq i \leq n$）
  • 左子树由 $[1, i-1]$ 构成，有 $G(i-1)$ 种可能
  • 右子树由 $[i+1, n]$ 构成，有 $G(n-i)$ 种可能
  • 根据乘法原理，以 i 为根的树有 $G(i-1) \times G(n-i)$ 种

因此：$G(n) = \sum_{i=1}^{n} G(i-1) \times G(n-i)$

画出递归树就能看到大量重叠：

        G(4)
       /  |  \  \
    G(0)G(3) G(1)G(2) G(2)G(1) G(3)G(0)
         /|\      |      |       /|\
      G(0)G(2)  G(0)G(1) ...   G(0)G(2)
           |         |              |
         G(0)G(1)  G(0)G(0)      G(0)G(1)

注意 G(2) 被计算了多次，G(1) 更是被反复计算。这就是典型的重叠子问题。

最优子结构的数学表达

虽然这道题不是求"最优"而是求"计数"，但它仍然具有类似的递归结构。更一般地，最优子结构可以表达为：

$$OPT[i] = \max_{k \in \text{decisions}} \{ f(OPT[j], \text{params}) \mid j < i \}$$ 其中 $f$ 是某个组合函数。对于不同的二叉搜索树问题，这个表达式变为： $$G[n] = \sum_{i=1}^{n} G[i-1] \cdot G[n-i]$$ 这其实就是著名的卡塔兰数（Catalan Number）的递推式。

实现：从暴力递归到记忆化

让我们用 Python 实现，展示从暴力递归到 DP 的演化过程：

# 暴力递归（会超时）
def numTrees_recursive(n):
    if n <= 1:
        return 1

    total = 0
    for i in range(1, n + 1):
        left = numTrees_recursive(i - 1)
        right = numTrees_recursive(n - i)
        total += left * right

    return total

# 记忆化递归（自顶向下DP）
def numTrees_memo(n):
    memo = {}

    def helper(n):
        if n in memo:
            return memo[n]
        if n <= 1:
            return 1

        total = 0
        for i in range(1, n + 1):
            left = helper(i - 1)
            right = helper(n - i)
            total += left * right

        memo[n] = total
        return total

    return helper(n)

# 自底向上DP
def numTrees(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1

    for nodes in range(2, n + 1):
        for root in range(1, nodes + 1):
            left = dp[root - 1]
            right = dp[nodes - root]
            dp[nodes] += left * right

    return dp[n]

从函数式编程的角度看，记忆化就是给纯函数加了一个缓存层。而自底向上的DP则是改变了计算顺序，确保计算某个值时，它依赖的值都已经计算好了。

9.2 状态定义的艺术

状态是什么：问题的阶段性描述

在动态规划中，"状态"是对问题在某个阶段的完整描述。好的状态定义应该包含做出最优决策所需的所有信息，同时又不包含冗余信息。从代数角度看，状态就是函数的参数，状态转移就是函数的递推关系。

理解状态的关键是问自己：在这个阶段，我需要知道什么信息才能做出最优决策？这些信息的组合就是状态。

好的状态定义标准

一个好的状态定义应该满足：

  1. 完备性：包含所有必要信息
  2. 最小性：不包含冗余信息
  3. 可转移性：能够从之前的状态推导出来
  4. 可计算性：最终答案能从状态中提取

让我们通过"打家劫舍"系列问题来理解状态定义的艺术。

LeetCode 198：打家劫舍 I

问题：不能偷相邻的房子，求最大收益。

第一次尝试：定义 dp[i] = 前 i 个房子的最大收益。 问题：不知道第 i-1 个房子有没有偷，无法决定第 i 个房子能不能偷。

改进：需要知道上一个房子的状态。

  • dp[i][0] = 前 i 个房子，第 i 个不偷的最大收益
  • dp[i][1] = 前 i 个房子，第 i 个偷的最大收益

状态转移：

dp[i][0] = max(dp[i-1][0], dp[i-1][1])  # 不偷第i个，前一个可偷可不偷
dp[i][1] = dp[i-1][0] + nums[i]         # 偷第i个，前一个必须不偷

再优化：其实不需要二维数组。 定义 dp[i] = 前 i 个房子能偷到的最大金额（第 i 个房子可偷可不偷）。

状态转移：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])
# 要么不偷第i个（dp[i-1]），要么偷第i个（dp[i-2] + nums[i]）

这个定义更简洁，因为它隐含了"是否偷第 i 个房子"的决策。

LeetCode 337：打家劫舍 III（树形DP）

问题：房子排列成二叉树，不能同时偷直接相连的房子。

这是树形DP，状态定义需要考虑树的结构：

def rob(root):
    def helper(node):
        if not node:
            return (0, 0)  # (不偷, 偷)

        left = helper(node.left)
        right = helper(node.right)

        # 不偷当前节点：左右子节点都可以偷或不偷，取最大
        not_rob = max(left) + max(right)

        # 偷当前节点：左右子节点都不能偷
        rob = node.val + left[0] + right[0]

        return (not_rob, rob)

    return max(helper(root))

这里状态是一个元组 (不偷该节点的最大值, 偷该节点的最大值)，这样父节点就有足够信息做决策。

从暴力搜索到状态抽象

设计状态的一般流程：

  1. 写出暴力搜索：明确每一步的选择
  2. 识别重复计算：哪些参数组合会重复出现
  3. 定义状态：这些参数就是状态
  4. 推导转移方程：根据选择写出递推关系

例如，对于打家劫舍问题：

# 暴力搜索
def rob_brute(nums, i):
    if i < 0:
        return 0
    # 每个房子都有偷或不偷两种选择
    return max(
        rob_brute(nums, i-1),           # 不偷第i个
        rob_brute(nums, i-2) + nums[i]  # 偷第i个
    )

# 观察到参数只有i，且会重复计算，所以状态就是i
# 加上记忆化
def rob_memo(nums):
    memo = {}
    def helper(i):
        if i < 0:
            return 0
        if i in memo:
            return memo[i]

        result = max(helper(i-1), helper(i-2) + nums[i])
        memo[i] = result
        return result

    return helper(len(nums)-1)

# 转为自底向上DP
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]

状态定义的常见模式

  1. 线性DP：dp[i] 表示前 i 个元素的最优解
  2. 区间DP：dp[i][j] 表示区间 [i,j] 的最优解
  3. 背包DP：dp[i][j] 表示前 i 个物品，容量为 j 的最优解
  4. 状态机DP：dp[i][state] 表示第 i 步，处于 state 状态的最优解
  5. 树形DP：每个节点返回多个值，表示不同选择下的最优解

理解了状态的本质，DP问题就变成了：

  1. 定义合适的状态（最难的一步）
  2. 找出状态转移方程
  3. 确定边界条件
  4. 计算顺序（递归还是迭代）

9.3 递推vs递归：两种实现方式

自顶向下：记忆化搜索

记忆化搜索本质上是递归加缓存。从函数式编程的角度，这是最自然的实现方式：我们定义一个纯函数，然后用高阶函数包装它，加上缓存功能。

记忆化搜索的优点：

  1. 思路直观：直接按照问题的递归定义编写
  2. 按需计算：只计算需要的状态
  3. 易于理解：代码结构清晰

让我们用 LeetCode 63"不同路径 II"来展示。问题：有障碍物的网格，从左上角到右下角有多少条路径？

# 记忆化搜索实现
def uniquePathsWithObstacles_memo(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    memo = {}

    def dfs(i, j):
        # 边界条件
        if i >= m or j >= n or obstacleGrid[i][j] == 1:
            return 0
        if i == m-1 and j == n-1:
            return 1

        # 查缓存
        if (i, j) in memo:
            return memo[(i, j)]

        # 递归计算：只能向右或向下
        paths = dfs(i+1, j) + dfs(i, j+1)
        memo[(i, j)] = paths
        return paths

    return dfs(0, 0)

用 Python 的装饰器，我们可以写出更优雅的记忆化：

from functools import lru_cache

def uniquePathsWithObstacles_elegant(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])

    @lru_cache(None)
    def dfs(i, j):
        if i >= m or j >= n or obstacleGrid[i][j] == 1:
            return 0
        if i == m-1 and j == n-1:
            return 1

        return dfs(i+1, j) + dfs(i, j+1)

    return dfs(0, 0)

自底向上：表格填充

自底向上的方法是按照依赖关系的顺序填表。这需要我们理清计算顺序，确保计算某个状态时，它依赖的状态都已经算好了。

# 自底向上DP
def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])

    if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
        return 0

    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    # 初始化第一行
    for j in range(1, n):
        if obstacleGrid[0][j] == 0:
            dp[0][j] = dp[0][j-1]

    # 初始化第一列
    for i in range(1, m):
        if obstacleGrid[i][0] == 0:
            dp[i][0] = dp[i-1][0]

    # 填表
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

两种方式的优劣对比

| 方面 | 记忆化搜索 | 自底向上DP |

方面 记忆化搜索 自底向上DP
思维难度 低（直接递归） 高（需要理清顺序）
代码复杂度 简单 中等
空间效率 只存储用到的状态 存储所有状态
时间效率 有函数调用开销 无函数调用开销
适用场景 状态空间稀疏 状态空间密集
边界处理 自然 需要特别初始化

实例对比：LeetCode 64 最小路径和

让我们用同一道题展示两种实现的差异：

# 方法1：记忆化搜索
def minPathSum_memo(grid):
    m, n = len(grid), len(grid[0])

    @lru_cache(None)
    def dfs(i, j):
        if i == m-1 and j == n-1:
            return grid[i][j]

        if i >= m or j >= n:
            return float('inf')

        return grid[i][j] + min(dfs(i+1, j), dfs(i, j+1))

    return dfs(0, 0)

# 方法2：自底向上DP
def minPathSum_dp(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    # 初始化
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    # 填表
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

    return dp[m-1][n-1]

# 方法3：空间优化的DP（后面会详细讲）
def minPathSum_optimized(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0

    for i in range(m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            if i == 0:
                dp[j] = dp[j-1] + grid[i][j]
            else:
                dp[j] = grid[i][j] + min(dp[j], dp[j-1])

    return dp[n-1]

选择建议

  1. 优先考虑记忆化搜索，如果： - 问题的递归定义很自然 - 状态空间很大但实际访问的状态较少 - 需要快速实现和调试

  2. 使用自底向上DP，如果： - 需要优化空间复杂度 - 状态转移有明确的拓扑序 - 面试官明确要求迭代实现

  3. 两种都写，在实际面试中： - 先用记忆化快速得到正确解 - 如果有时间，再改写成自底向上并优化空间

9.4 空间优化：滚动数组与状态压缩

观察状态依赖关系

空间优化的核心是观察状态转移中的依赖关系。如果 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，那么我们不需要保存所有的 dp[0] 到 dp[n]，只需要保存最近的两个值即可。

这种优化的数学基础是：如果状态转移只依赖于有限个之前的状态，那么空间复杂度可以降到常数。

滚动数组技巧

滚动数组是指用固定大小的数组循环使用，模拟整个DP数组。最常见的是二维DP优化到一维。

让我们通过股票买卖问题来深入理解空间优化。

LeetCode 309：最佳买卖股票时机含冷冻期

问题：卖出股票后，无法在第二天买入（冷冻期为1天）。

首先写出完整的状态定义：

  • hold[i]：第i天持有股票的最大利润
  • sold[i]：第i天卖出股票的最大利润
  • rest[i]：第i天不持有股票且不在冷冻期的最大利润

状态转移：

hold[i] = max(hold[i-1], rest[i-1] - prices[i])  # 继续持有 或 买入
sold[i] = hold[i-1] + prices[i]                   # 卖出
rest[i] = max(rest[i-1], sold[i-1])              # 继续休息 或 解冻

观察依赖关系：每个状态只依赖前一天的状态，所以可以用滚动变量优化：

def maxProfit_with_cooldown(prices):
    if not prices:
        return 0

    # 完整DP版本
    n = len(prices)
    hold = [0] * n
    sold = [0] * n
    rest = [0] * n

    hold[0] = -prices[0]
    sold[0] = 0
    rest[0] = 0

    for i in range(1, n):
        hold[i] = max(hold[i-1], rest[i-1] - prices[i])
        sold[i] = hold[i-1] + prices[i]
        rest[i] = max(rest[i-1], sold[i-1])

    return max(sold[n-1], rest[n-1])

def maxProfit_optimized(prices):
    if not prices:
        return 0

    # 空间优化版本：只用三个变量
    hold = -prices[0]
    sold = 0
    rest = 0

    for price in prices[1:]:
        prev_hold = hold
        prev_sold = sold

        hold = max(hold, rest - price)
        sold = prev_hold + price
        rest = max(rest, prev_sold)

    return max(sold, rest)

LeetCode 714：买卖股票的最佳时机含手续费

每笔交易需要支付手续费。这道题展示了另一种空间优化模式：

def maxProfit_with_fee(prices, fee):
    # 方法1：二维DP
    n = len(prices)
    dp = [[0, 0] for _ in range(n)]  # dp[i][0]不持有, dp[i][1]持有
    dp[0][0] = 0
    dp[0][1] = -prices[0]

    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

    return dp[n-1][0]

def maxProfit_optimized(prices, fee):
    # 方法2：空间优化到O(1)
    cash = 0  # 不持有股票的最大利润
    hold = -prices[0]  # 持有股票的最大利润

    for price in prices[1:]:
        prev_cash = cash
        cash = max(cash, hold + price - fee)
        hold = max(hold, prev_cash - price)

    return cash

状态压缩的时机

并非所有DP都能进行空间优化。能够优化的前提是：

  1. 有限依赖：当前状态只依赖有限个之前的状态
  2. 顺序计算：计算顺序是固定的，不会回头访问
  3. 单向转移：状态转移是单向的，不存在环

常见的可优化模式：

# 模式1：只依赖前一个状态
# 原始：dp[i] = f(dp[i-1])
# 优化：curr = f(prev)

# 模式2：依赖前两个状态（如斐波那契）
# 原始：dp[i] = dp[i-1] + dp[i-2]
# 优化：curr = prev1 + prev2

# 模式3：二维DP，只依赖上一行
# 原始：dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# 优化：dp[j] = f(dp[j], dp[j-1])

实战技巧：01背包的空间优化

01背包是经典的空间优化案例。原始状态：dp[i][w] 表示前i个物品，容量w的最大价值。

# 二维DP版本
def knapsack_2d(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            # 不选第i个物品
            dp[i][w] = dp[i-1][w]
            # 选第i个物品（如果能装下）
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w-weights[i-1]] + values[i-1])

    return dp[n][W]

# 一维优化版本（关键：逆序遍历）
def knapsack_1d(weights, values, W):
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        # 必须逆序！否则会重复使用物品
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

为什么要逆序？ 因为 dp[w] 依赖 dp[w-weight[i]]，如果正序，dp[w-weight[i]] 已经被这一轮更新过了，相当于物品i被使用了多次。逆序保证了我们用的是上一轮的值。

空间优化的思维框架

  1. 画出依赖图：明确每个状态依赖哪些之前的状态
  2. 找出必要状态：确定同时需要保存多少个状态
  3. 设计更新策略：确定是否需要临时变量、是否需要逆序
  4. 验证正确性：确保优化后的依赖关系没有改变

记住：空间优化是锦上添花，不是必需品。面试时先写出正确的解法，再考虑优化。但理解空间优化的原理，能让你对DP的本质有更深的认识。

本章小结

动态规划的本质是带缓存的递归。从函数式编程的角度看，DP就是对纯函数进行记忆化，避免重复计算。掌握DP的关键不在于背诵转移方程，而在于理解问题的递归结构。

核心要点回顾

  1. 两个必要条件： - 重叠子问题：递归会重复计算相同的子问题 - 最优子结构：大问题的最优解包含子问题的最优解

  2. 状态设计原则： - 状态要包含做决策所需的所有信息 - 状态要尽可能简洁，不包含冗余 - 好的状态定义让转移方程自然而然

  3. 两种实现方式： - 记忆化搜索：自顶向下，代码直观，适合稀疏状态空间 - 自底向上DP：迭代填表，无递归开销，便于空间优化

  4. 空间优化技巧： - 观察状态依赖，只保存必要的历史状态 - 滚动数组：用固定空间模拟整个数组 - 逆序遍历：处理依赖关系，避免覆盖

关键公式总结

通用状态转移框架： $$dp[i] = \min/\max_{k \in decisions} \{ f(dp[j], params) \mid j < i \}$$

常见DP模式：

  • 线性DP：$dp[i] = f(dp[i-1], dp[i-2], ...)$
  • 区间DP：$dp[i][j] = f(dp[i][k], dp[k+1][j])$
  • 背包DP：$dp[i][w] = \max(dp[i-1][w], dp[i-1][w-weight] + value)$
  • 状态机DP：$dp[i][state] = f(dp[i-1][prev_states])$

常见陷阱与错误 (Gotchas)

1. 状态定义不完整

错误示例：打家劫舍问题只定义"前i个房子的最大收益"，忽略了第i个房子是否被偷的信息。

调试技巧：问自己"根据当前状态，能否唯一确定下一步的决策？"如果不能，说明状态定义缺少信息。

2. 边界条件处理不当

常见错误：

# 错误：忘记处理空数组
def rob(nums):
    dp = [0] * len(nums)  # nums为空时会报错
    dp[0] = nums[0]
    # ...

# 正确：先检查边界
def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    # ...

调试技巧：总是先处理n=0, n=1的特殊情况。

3. 状态转移方程错误

错误类型：

  • 漏掉某种决策分支
  • 搞混max和min
  • 下标越界

调试方法：

# 添加打印语句跟踪状态转移
def debug_dp(nums):
    dp = [0] * len(nums)
    for i in range(len(nums)):
        # 打印当前状态和决策
        print(f"i={i}, considering: {options}")
        dp[i] = max(options)
        print(f"dp[{i}] = {dp[i]}")
    return dp[-1]

4. 空间优化时覆盖了需要的值

典型错误：01背包正序遍历

# 错误：正序会导致物品被重复使用
for w in range(weight, W + 1):
    dp[w] = max(dp[w], dp[w - weight] + value)

# 正确：逆序确保使用上一轮的值
for w in range(W, weight - 1, -1):
    dp[w] = max(dp[w], dp[w - weight] + value)

调试技巧：画出依赖关系图，确认更新顺序不会破坏依赖。

5. 记忆化搜索的陷阱

陷阱1：可变对象作为缓存键

# 错误：列表不能作为字典的键
@lru_cache(None)
def solve(arr):  # arr是列表，会报错
    ...

# 正确：转为元组
@lru_cache(None)
def solve(arr_tuple):  # 传入tuple(arr)
    ...

陷阱2：缓存了非纯函数

# 错误：函数依赖外部状态
prices = [1, 2, 3]
@lru_cache(None)
def maxProfit(i):
    return prices[i]  # 依赖外部变量prices

# 正确：将所有依赖作为参数
@lru_cache(None)
def maxProfit(i, prices_tuple):
    return prices_tuple[i]

6. 整数溢出

在某些语言（如C++、Java）中，DP的中间结果可能溢出：

# Python不会溢出，但其他语言要注意
# C++: 使用long long
# Java: 使用long或BigInteger

实战调试流程

  1. 先写暴力递归，确保理解问题
  2. 打印递归调用，观察重复计算
  3. 加入记忆化，验证正确性
  4. 改写为迭代，对比结果
  5. 尝试空间优化，确保结果不变

记住：DP的难点不在于编码，而在于识别问题类型和设计状态。多做题，多总结模式，逐渐就会形成直觉。当你能够看到一个问题就立刻想到"这是个XX类型的DP"时，你就真正掌握了动态规划。