计算机程序设计艺术：用动态规划解决经典问题

动态规划（Dynamic Programming，DP）不是某一种固定算法，而是一套组织计算的思路：把原问题拆成规模较小的子问题，保存已经算出的结果，避免重复计算，再按照依赖关系组合出答案。

这套思路常用于序列、路径、资源分配和字符串等问题。它能把某些指数级的穷举搜索降到多项式时间，但并不意味着“能拆成小问题就应该用 DP”。状态是否足够、子问题之间如何依赖、输入规模是否允许所需的时间与空间，都会影响方案是否成立。

一、什么情况下适合用动态规划

判断一个问题是否适合 DP，可以先检查两个特征。

• 最优子结构：原问题的最优解可以由子问题的最优解组合得到。例如，容量为 c 的背包最优解，可以通过考虑是否选择某件物品，转化为更小容量下的最优解。
• 重叠子问题：递归拆分时，同一子问题会被重复求解。若每次递归都产生互不相同的子问题，缓存的帮助可能有限。

满足这两个特征后，还要把“状态”定义清楚。状态是能够完整描述一个子问题的信息。例如，只记录背包容量还不够；对于逐件处理的背包问题，还需要明确已经处理到哪一件物品。写成二维状态时通常是 dp[i][c]，表示只考虑前 i 件物品、容量不超过 c 时能取得的最大价值。

设计状态时可依次回答三个问题：状态代表什么？初始状态是什么？当前状态依赖哪些更小的状态？随后根据依赖关系决定计算顺序。若依赖关系存在环，或者某个状态依赖尚未定义的结果，就需要重新审视状态设计或问题模型。

二、递归记忆化与迭代填表

动态规划常见的两种写法是递归记忆化和自底向上的迭代。

记忆化递归从目标问题出发，遇到未计算的子问题时才递归求解，并缓存结果。它通常容易对应数学递推式，适合状态空间稀疏或递归结构直观的题目。但递归深度可能受语言运行环境限制，缓存也会占用空间。

迭代 DP 从较小的子问题开始，按依赖顺序填表。它通常更容易控制递归深度，也便于压缩空间。代价是必须仔细安排循环顺序，避免覆盖尚未使用的旧状态。

三、从斐波那契数列看重复计算

斐波那契数列满足 F(0)=0、F(1)=1，以及 F(n)=F(n-1)+F(n-2)。直接递归会反复计算相同项；例如计算 F(5) 时，F(3) 会被求解不止一次。记忆化能保存中间结果，而迭代写法还可以把空间从保存全部结果降到常数级。

def fibonacci(n):
    """返回第 n 个斐波那契数，要求 n 是非负整数。"""
    if not isinstance(n, int) or isinstance(n, bool) or n < 0:
        raise ValueError("n 必须是非负整数")

    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


assert fibonacci(0) == 0
assert fibonacci(1) == 1
assert fibonacci(10) == 55
print(fibonacci(10))

循环执行 n 次，时间复杂度为 O(n)；只保留两个状态，额外空间为 O(1)。Python 整数可以表示任意精度结果，但数字位数会随 n 增长，因此大输入下每次加法并非严格的常数时间。程序也不会为 n 设置任意上限：实际可处理范围仍受运行时间、内存及应用自身限制。

四、经典问题：0/1 背包

有 n 件物品，第 i 件物品重量为 weights[i]、价值为 values[i]。每件物品只能选或不选一次，背包容量为 capacity，目标是让总重量不超过容量时的总价值最大。

二维状态转移可以写成：处理第 i 件物品时，不选它，或在装得下时选择它。用一维数组压缩空间后，需要从大到小遍历容量。这样更新 dp[c] 时，dp[c - weight] 仍属于处理当前物品之前的状态，从而保证一件物品不会被重复选取。

def knapsack_01(weights, values, capacity):
    """
    返回 0/1 背包的最大总价值。
    weights、values 应为等长的非负整数序列；
    capacity 应为非负整数。
    """
    if not isinstance(capacity, int) or isinstance(capacity, bool) or capacity < 0:
        raise ValueError("capacity 必须是非负整数")
    if len(weights) != len(values):
        raise ValueError("weights 和 values 长度必须相同")
    if any(not isinstance(w, int) or isinstance(w, bool) or w < 0
           for w in weights):
        raise ValueError("重量必须是非负整数")
    if any(not isinstance(v, int) or isinstance(v, bool)
           for v in values):
        raise ValueError("价值必须是整数")

    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for current_capacity in range(capacity, weight - 1, -1):
            dp[current_capacity] = max(
                dp[current_capacity],
                dp[current_capacity - weight] + value
            )
    return dp[capacity]


assert knapsack_01([2, 3, 4], [4, 5, 7], 5) == 9
assert knapsack_01([], [], 0) == 0
print(knapsack_01([2, 3, 4], [4, 5, 7], 5))

时间复杂度为 O(n × capacity)，额外空间为 O(capacity)。这里的复杂度与容量的数值相关，而不是容量所需的二进制位数；如果容量很大，即使物品数量不多，数组也可能难以分配。因此，不能仅凭“代码是多项式复杂度”就认定它适用于任意输入规模。

示例允许重量为零：每件零重量物品仍只处理一次，降序循环会将其价值计入至多一次。负重量没有合理的背包含义，因此拒绝。价值允许为负数；由于可以不选物品，负价值通常不会改善最优结果。

常见错误：把容量循环改成从小到大，会让本轮刚更新的状态再次参与计算，解法就变成可重复选择物品的完全背包，而不是 0/1 背包。若要恢复选了哪些物品，还需保存决策信息，或设计额外的回溯方法；只有一维最大价值数组并不能直接还原完整方案。

五、最长递增子序列

给定整数序列，最长递增子序列（LIS）要求元素保持原有相对顺序，但不要求连续。下面的二分查找方法求的是严格递增子序列长度，时间复杂度为 O(n log n)。

数组 tails 的第 k 个位置，记录长度为 k+1 的递增子序列中，尽可能小的末尾值。遍历到一个数时，用二分查找找到第一个大于或等于它的位置并替换。较小的末尾值有利于后续接入更多元素，但 tails 本身不一定是一条真实的子序列。

from bisect import bisect_left


def lis_length(numbers):
    """返回严格递增子序列的长度。"""
    tails = []
    for number in numbers:
        position = bisect_left(tails, number)
        if position == len(tails):
            tails.append(number)
        else:
            tails[position] = number
    return len(tails)


assert lis_length([]) == 0
assert lis_length([3, 1, 2, 5, 4]) == 3
assert lis_length([2, 2, 2]) == 1
print(lis_length([3, 1, 2, 5, 4]))

bisect_left 返回第一个大于或等于当前值的位置，因此相同的数字会替换原位置，不会延长严格递增序列。如果题目要求非递减序列（允许相邻相等），应改用 bisect_right。若需要输出具体子序列，仅保存 tails 不够，还要额外维护前驱及对应位置。

六、编辑距离与二维状态

编辑距离衡量两个字符串之间的差异。常见定义允许插入、删除和替换单个字符，且每种操作代价均为 1。设 dp[i][j] 表示把第一个字符串的前 i 个字符变成第二个字符串的前 j 个字符所需的最小操作数。

初始边界是 dp[i][0] = i（逐个删除）和 dp[0][j] = j（逐个插入）。如果末尾字符相同，继承 dp[i-1][j-1]；否则在删除、插入、替换三种操作中取最小值并加一。

def edit_distance(source, target):
    """
    返回插入、删除、替换代价均为 1 的编辑距离。
    参数应为字符串。
    """
    if not isinstance(source, str) or not isinstance(target, str):
        raise TypeError("source 和 target 必须是字符串")

    previous = list(range(len(target) + 1))

    for i, source_char in enumerate(source, start=1):
        current = [i] + [0] * len(target)
        for j, target_char in enumerate(target, start=1):
            if source_char == target_char:
                current[j] = previous[j - 1]
            else:
                current[j] = 1 + min(
                    previous[j],      # 删除
                    current[j - 1],   # 插入
                    previous[j - 1]   # 替换
                )
        previous = current

    return previous[-1]


assert edit_distance("", "abc") == 3
assert edit_distance("kitten", "sitting") == 3
assert edit_distance("same", "same") == 0
print(edit_distance("kitten", "sitting"))

时间复杂度为 O(mn)，其中 m、n 是两个字符串的长度；滚动两行后，额外空间为 O(n)。Python 字符串按 Unicode 码点进行迭代，因此这里计算的是码点序列上的距离，不一定等同于人类感知的字符数量。例如，带组合附加符号的文本可能由多个码点构成。若业务要求按字素簇处理，需要先按相应的文本分段规则切分，再在切分后的序列上计算。

七、常见错误与边界检查

• 状态定义不完整：如果子问题还依赖“处理到第几项”“上一步选择了什么”等信息，却未包含在状态中，转移可能混合不相容的情况。
• 初始值不合适：最小值、最大值问题的不可达状态通常要用适当的哨兵值表示；随意填 0 可能让不存在的路径参与比较。哨兵值与加法运算结合时，也要避免溢出或产生错误结果。
• 循环方向错误：一维数组压缩会改变状态被覆盖的时机。0/1 背包容量降序、完全背包容量升序，是依赖关系不同造成的，不应背成无条件规则。
• 边界漏处理：空序列、容量为零、空字符串、只有一个元素等情况都值得单独检查。很多 DP 错误并非转移式本身错误，而是边界没有与转移保持一致。
• 复杂度估算不完整：除了循环次数，还要看状态数量、每个状态的计算成本、整数或字符串操作的成本，以及存储整张表所需的内存。
• 误以为缓存总能提速：若子问题几乎不重复，记忆化的查表和存储开销可能没有收益；如果状态空间巨大，也可能耗尽内存。

八、如何选择 DP 与其他方法

若问题要求在所有选择中找最优解，可以先考虑暴力搜索，明确每一步的选择，再观察搜索树中是否重复出现相同子问题。若有大量重复，DP 或记忆化搜索通常值得尝试；若问题满足特定结构，也可能存在贪心算法、双指针、图算法或数学方法，计算成本更低。

DP 的适用性还取决于状态数量是否可控。背包的 O(n × capacity) 虽然对容量呈线性，但容量可能以很少的位数表示一个极大的数值，这类复杂度常称为伪多项式。不同问题的状态空间差异很大，设计前应估算输入上限、最坏状态数和内存占用，而不是只看示例规模。

九、DP 与安全用途

动态规划是通用算法设计方法，本身不是加密、认证或输入校验机制。它可以用于安全相关软件中的优化子问题，但一个 DP 结果正确，并不自动意味着整个系统安全。例如，不能用编辑距离替代密码验证，不能用背包算法替代经过分析的密码学构造，也不能把“运行时间有限”当成抵御拒绝服务的保证。

对于接收外部输入的程序，应依据业务需求设置合理的长度、容量和状态数量上限，并在分配内存或进入高成本计算之前检查这些限制。上述示例只验证了部分参数类型与非负条件，没有替具体业务定义最大输入规模，也不保证对任意大输入都能及时完成。部署时还需要结合资源配额、超时策略和错误处理进行评估。

结语

使用动态规划时，最重要的工作不是套用某个模板，而是把问题精确地表达为状态、边界和转移。斐波那契数列展示了如何避免重复计算；0/1 背包展示了状态压缩和循环方向的影响；最长递增子序列说明优化方法可能改变状态的含义；编辑距离则体现了二维前缀状态如何处理字符串变换。

动手实现时，可以先写出小规模、便于验证的状态定义，再检查空输入和极端边界，用简单用例对照预期结果，最后评估时间与空间复杂度。状态正确、依赖清晰、边界明确，才是动态规划代码可靠运行的基础。