13.1 动态规划入门

前置：递归、分治与回溯。本页从斐波那契的重复调用出发，建立状态、转移、边界与计算顺序，再用爬楼梯和相邻房屋选择检验模型。

同一个状态，算一次就够了

不同的选择路径可能到达同一个状态。朴素递归会再次展开相同的后续计算；记忆化则保存第一次得到的答案，下次直接读取。

动态规划适合具有重叠子问题的问题；若还要求从局部子答案组合出当前答案，就要把状态和转移写清。常见步骤是：

1. 状态：函数参数或表格下标分别代表什么；
2. 转移：当前状态依赖哪些更小状态；
3. 边界：哪些状态可以直接回答；
4. 顺序：依赖项必须先于当前状态可用；
5. 答案：最终读取哪个状态，是否需要还原方案。

“有递归”不是 DP，“用了数组”也不是 DP。核心是同一状态的答案只求一次，并且转移覆盖所有合法选择。

斐波那契：同一转移的两种方向

前三个函数要求非负整数 n；最后一个接收非负整数的可迭代对象，只遍历一次，允许一个都不选，空输入返回 0。非法数值抛 ValueError。

from functools import lru_cache

def _require_non_negative(n):
    if not isinstance(n, int) or n < 0:
        raise ValueError("n must be a non-negative integer")

def fib_top_down(n):
    _require_non_negative(n)

    @lru_cache(maxsize=None)
    def solve(index):
        if index < 2:
            return index
        return solve(index - 1) + solve(index - 2)

    return solve(n)

def fib_bottom_up(n):
    _require_non_negative(n)
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

def climb_stairs(n):
    """每次走 1 或 2 阶；空楼梯有一种“不走”的方案。"""
    _require_non_negative(n)
    previous, current = 1, 1  # ways(0), ways(1)
    for _ in range(n):
        previous, current = current, previous + current
    return previous

def max_non_adjacent_sum(values):
    """遍历非负整数，返回不选择相邻项时的最大和；允许空选择。"""
    skip, take = 0, 0
    for value in values:
        if not isinstance(value, int) or value < 0:
            raise ValueError("values must be non-negative integers")
        skip, take = max(skip, take), skip + value
    return max(skip, take)

if __name__ == "__main__":
    for n in range(101):
        assert fib_top_down(n) == fib_bottom_up(n)

    assert fib_bottom_up(50) == 12_586_269_025
    assert climb_stairs(0) == 1
    assert climb_stairs(1) == 1
    assert climb_stairs(10) == 89
    assert max_non_adjacent_sum([2, 7, 9, 3, 1]) == 12
    assert max_non_adjacent_sum([]) == 0
    print("DP 入门检查通过")

Top-down 从目标状态向依赖递归，在这段单线程代码中每个 index 只展开一次；bottom-up 从边界向目标迭代。按一次加法为常数操作计，二者时间都是 Θ(n+1)。记忆化保存 O(n+1) 个缓存项并使用 O(n+1) 递归栈；迭代 Fibonacci 只保留两个相邻状态。缓存定义在函数内部，每次公开调用都会新建，调用 fib_top_down(50) 后再调用 fib_top_down(51) 不会沿用前一份结果。lru_cache 文档说明了 maxsize=None 不设缓存项数量上限。

Python 整数可按内存扩展。Java int 在 Fibonacci 很早就会溢出，long 也只能覆盖有限下标；需要更大精确值时应使用 BigInteger 或明确采用模运算。F(n) 的位数为 Θ(n)。若按位计内存，迭代版本保留的整数占 Θ(n) 位，缓存全部结果则占 Θ(n²) 位；使用线性时间大整数加法时，两种版本的加法总成本均为 Θ(n²)。所以“两个状态”不等于“常数位内存”。

怎样从递归参数得到状态

朴素 Fibonacci 的结果只由 n 决定，因此 n 足以标识状态。若结果还取决于当前位置、剩余容量或另一个字符串下标，这些量也必须进入缓存键或 DP 维度。漏掉一个会把不同子问题错误合并。

反过来，若某个参数不影响后续答案，就不应放进状态。多余维度会增加时间和空间，也可能掩盖真正的转移关系。

重叠子问题

fib(n-1) 与 fib(n-2) 都会继续请求 fib(n-3)。这就是相同参数的子问题重复出现。分治归并排序的左右区间互不重叠，所以无需缓存相同区间。

最优子结构

不相邻项选择的状态可以写成“处理完前 i 项时的最大和”。以下公式用从 1 开始的物品编号，第 i 项只有两种合法决定：

不选 i：best[i-1]
选 i：best[i-2] + value[i]

令 best[0]=0，处理第 1 项时把不存在的前缀也按 0 计。代码的 skip 表示前一项未选时的最优和，take 表示前一项已选时的最优和；初始的两个 0 对应空前缀。Python 会先算完赋值右侧，因此新的 take 读取的是旧 skip。取两种决定的较大值即可，因为它们已覆盖所有合法方案，并且各自使用对应前缀的最优子答案。所谓最优子结构不是一句口号，而是这段“若子答案不优，就能替换并改善整体”的论证。

表格方向为什么会影响答案

若 dp[i] 依赖 dp[i-1]，就必须从小到大计算。二维表格同理：先画箭头，再决定循环方向。空间压缩时更要谨慎，因为当前轮写入可能覆盖上一轮仍需要的值。

Top-down 通常只访问从目标可达的状态，但受递归深度限制；bottom-up 没有递归栈，却可能计算最终用不到的状态。工程选择取决于状态图稀疏程度、深度、常数开销与还原路径要求。

常见错误的定位顺序

1. 用一句完整的话写出状态含义，包括“前多少项”和“容量恰好还是不超过”。
2. 列出每个合法选择，确认转移没有漏分支或重复使用元素。
3. 单独写空输入与最小输入的答案。
4. 画依赖箭头，检查循环顺序和空间压缩覆盖。
5. 用小规模暴力枚举做 oracle，再测试随机输入。
6. 若要还原方案，额外保存父选择，不能只留最终数值。

动手建立状态

1. 给 fib_top_down 统计实际展开的不同参数数量。
2. 把 max_non_adjacent_sum 改成同时返回选中的下标。
3. 若房屋价值允许负数，“可以一个都不选”和“至少选一个”会产生什么不同边界？
4. 写出网格路径计数的状态与边界，再决定能否压缩为一维。
5. 比较 climb_stairs(0) 返回 0 与 1 的两种业务语义。

状态定义决定复用范围

动态规划不是“把递归改成数组”，而是为可复用状态建立唯一含义。状态、转移、边界和顺序彼此一致后，记忆化与表格法只是两种求值方向。

下一篇进入 0-1 背包、LCS 与编辑距离，把一维状态扩展到容量和双序列。