动态规划

动态规划(Dynamic Programming, DP)是一种将复杂问题分解为更小子问题并存储子问题解以避免重复计算的方法,常用于求解最优化与计数类问题。

两个核心性质

• 最优子结构:问题的最优解可以由子问题的最优解组合得到。
• 重叠子问题:在递归求解过程中,相同的子问题会被反复计算多次,适合用记忆化或递推避免冗余。

满足这两点的问题,通常都能改写为 DP 求解。常见步骤为:定义状态、写出状态转移方程、确定初始状态与计算顺序。

记忆化搜索 vs 递推

两种实现方式本质等价。记忆化搜索采用自顶向下的递归,首次计算某个状态后将结果缓存,后续直接返回;递推采用自底向上的方式,按拓扑序从小状态逐步推导大状态,通常更省栈空间且更易做空间优化。

# 斐波那契:记忆化搜索 vs 递推
from functools import lru_cache

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

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

经典问题

0-1 背包

有 N 件物品,每件重 w[i]、价值 v[i],背包容量 W,每件至多选一次,求最大价值。dp[i][j] 表示前 i 件物品在容量 j 下的最大价值,状态转移为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]),时间 O(NW)。

最长公共子序列(LCS)

给定字符串 A、B,求最长的公共子序列。dp[i][j] 表示 A 前 i 个字符与 B 前 j 个字符的 LCS 长度,转移为:

if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

最长上升子序列(LIS)

求数组中严格递增的最长子序列长度。朴素 DP 为 O(n²):dp[i] = max(dp[j] + 1) for j < i and a[j] < a[i]。用二分查找 + 耐心排序可将复杂度优化到 O(n log n)。

空间优化

多数 DP 只需上一行或前几行的状态,可将二维数组滚动为一维:

• 0-1 背包:内层循环逆序遍历 j,即可在 dp[j] = max(dp[j], dp[j-w[i]] + v[i]) 中复用一维数组。
• LCS:用两行交替更新,或单行逆序 + 临时变量实现 O(min(|A|, |B|)) 空间。

掌握 DP 的关键在于多做练习、积累状态设计的经验,同时关注能否通过滚动数组、单调队列、矩阵快速幂等技巧进一步降低复杂度。