第 50 课 - 动态规划入门

学习目标

完成本课后，你将能够：

理解动态规划（Dynamic Programming, DP）的核心思想与适用场景。
掌握动态规划的两种实现方式：记忆化搜索与递推（制表法）。
学会识别问题的最优子结构和重叠子问题特性。
能够为简单的动态规划问题（如斐波那契数列、爬楼梯）定义状态并写出状态转移方程。

核心概念

想象一下，你要计算一条复杂路径的最短距离。如果你把路程分成很多小段，每一段的最短距离都已经知道了，那么整条路的最短距离就可以通过组合这些小段的最优解得到。这就是动态规划的精髓：将一个复杂问题分解为更小的、相互重叠的子问题，通过保存子问题的解（避免重复计算），最终自底向上地求解原问题。

动态规划适用于具有以下两个特性的问题：

最优子结构 (Optimal Substructure)：问题的最优解包含了其子问题的最优解。
重叠子问题 (Overlapping Subproblems)：在递归求解过程中，相同的子问题会被反复计算多次。

DP 有两种经典的实现方式：

记忆化搜索 (Memoization)：这是“自顶向下”的递归方法。从原问题开始递归分解，在递归过程中，将每个子问题的解缓存起来。当再次遇到相同的子问题时，直接返回缓存的结果。
递推 / 制表法 (Tabulation)：这是“自底向上”的迭代方法。我们从最小的子问题开始，按照某种顺序（如从小到大）依次计算并填入一个表（通常是数组）中，最终得到原问题的解。

这两种方法的核心区别在于求解方向，但都需要我们明确两点：

状态定义：你需要什么样的参数来唯一标识一个子问题？通常对应DP数组的索引。
状态转移方程：如何通过已解决的、更小的子问题来推导当前子问题的解？

下面，我们通过经典的斐波那契数列问题来具体看看这两种方法。斐波那契数列定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n>1)。

代码示例

示例1：使用记忆化搜索（自顶向下）计算斐波那契数

def fib_memoization(n, memo={}):
    """
    使用记忆化（缓存）计算斐波那契数列的第n项。
    :param n: 要计算的项数
    :param memo: 用于缓存已计算结果的字典
    :return: F(n)
    """
    # 基础情况
    if n <= 1:
        return n
    
    # 如果这个子问题已经计算过，直接从缓存中返回结果
    if n in memo:
        return memo[n]
    
    # 否则，计算它，并将结果存入缓存
    memo[n] = fib_memoization(n-1, memo) + fib_memoization(n-2, memo)
    return memo[n]

# 测试
print(fib_memoization(10)) # 输出: 55
print(fib_memoization(50)) # 输出: 12586269025 (没有记忆化会极慢)

示例2：使用递推法（自底向上）计算斐波那契数

def fib_tabulation(n):
    """
    使用递推（制表法）计算斐波那契数列的第n项。
    :param n: 要计算的项数
    :return: F(n)
    """
    # 处理边界情况
    if n <= 1:
        return n
    
    # 创建DP表，dp[i] 用于存储 F(i)
    dp = [0] * (n + 1)
    
    # 初始化基础情况
    dp[0] = 0
    dp[1] = 1
    
    # 从2到n，依次填充DP表
    for i in range(2, n + 1):
        # 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# 测试
print(fib_tabulation(10)) # 输出: 55
print(fib_tabulation(50)) # 输出: 12586269025

实践练习

练习 1：爬楼梯（简单）

问题描述：假设你正在爬楼梯，需要 n 步才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？ (提示：这与斐波那契数列非常相似。第 n 级台阶的方法数 = 第 n-1 级台阶的方法数 + 第 n-2 级台阶的方法数。) 要求：分别使用记忆化搜索和递推法实现。 预期输出：

climb_stairs_memo(3) -> 2
climb_stairs_tab(3) -> 2

练习 2：最小花费爬楼梯（简单）

问题描述：数组的每个索引作为一个阶梯，第 i 个阶梯对应着一个非负体力消耗值 cost[i]（索引从 0 开始）。每当你爬上一个阶梯，你都要消耗对应的体力值。你可以选择从下标为 0 或 1 的元素开始。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。要求：定义状态 dp[i] 表示到达第 i 个阶梯的最小花费，写出状态转移方程，并用递推法实现。 预期输出：

min_cost_climbing_stairs([10, 15, 20]) -> 15 (从索引1开始，花费15直接到顶)
min_cost_climbing_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) -> 6

常见错误

忽略最优子结构：试图用DP解决不具有最优子结构的问题（例如，寻找图中的最长简单路径），这会导致错误的解。
记忆化遗漏或错误：
- 在记忆化搜索中，忘记将计算结果存入缓存。
- 在递推法中，DP数组的初始化条件设置错误（例如，斐波那契数列的 dp[0] 和 dp[1]）。
状态转移方程定义不清：这是最核心的难点。初学者常常无法清晰地定义 dp[i] 代表什么，以及它如何由之前的 dp 值推导而来。
递归深度与效率：在记忆化搜索中，如果问题规模很大，递归调用可能导致栈溢出。递推法通常是更安全的选择。

小结

动态规划的本质：通过存储子问题的解来避免重复计算，用空间换时间。
适用条件：问题必须具备最优子结构和重叠子问题。
实现路径：
- 记忆化搜索：递归 + 缓存，自顶向下。
- 递推（制表法）：迭代 + DP数组，自底向上，通常效率更高且不易栈溢出。
解题关键：清晰地定义状态 (dp[i] 是什么？)，并找出正确的状态转移方程。
从斐波那契和爬楼梯开始，它们是理解DP基础概念的绝佳范例。掌握了它们，你就拥有了挑战更复杂DP问题（如背包问题、路径问题等）的钥匙。

下一课预告：我们将深入探讨两个最基础的DP问题——斐波那契数列与爬楼梯，并分析它们的时间与空间复杂度，以及如何进一步优化。

练习编辑器

rust