第八章：动态规划

本章目标

本章学习动态规划。DP 适合有重叠子问题和最优子结构的问题，核心是定义状态并复用中间结果。

你会从爬楼梯入门，再用 0/1 背包理解一维数组优化。

核心概念

状态描述子问题，状态转移描述如何从更小问题推出当前问题，初始化保证起点正确。

动态规划不是套公式。先问 dp[i] 表示什么，再问最后答案在哪里，最后检查遍历顺序是否满足依赖。

Python 示例

爬楼梯的状态转移是 dp[i] = dp[i - 1] + dp[i - 2]。

def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

0/1 背包一维 DP 要倒序遍历容量，避免同一物品被重复使用。

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

复杂度与常见误区

爬楼梯优化后时间复杂度 O(n)，空间复杂度 O(1)。0/1 背包一维写法时间复杂度 O(nC)，空间复杂度 O(C)。

常见误区是背包容量正序遍历。正序会让当前物品在同一轮被多次使用，变成完全背包语义。

本章要点

写 DP 时按状态、转移、初始化、遍历顺序、答案位置五步检查。

动态规划的难点在建模。代码往往很短，但状态定义必须和题目目标精准对应。