动态规划

什么是动态规划

动态规划（Dynamic Programming，DP）适用于具有以下两个特征的问题：

与分治法的区别

方面	分治法	动态规划
子问题重叠	无重叠（各子问题独立）	有重叠，存储复用
典型例子	归并排序、快速排序	背包问题、LCS
存储策略	不存储中间结果	记忆化或 DP 表

DP 解题四步框架

从递归到 DP：以 Fibonacci 为例

Step 1：朴素递归（指数级重复计算）

def fib_v1(n):
    if n <= 1: return n
    return fib_v1(n-1) + fib_v1(n-2)
# 时间 O(2^n) — fib(50) 需要约 10^15 次调用，实际不可行

Step 2：备忘录（自顶向下 DP）

def fib_v2(n, memo=None):
    if memo is None: memo = {}
    if n in memo: return memo[n]   # 命中缓存
    if n <= 1: return n
    memo[n] = fib_v2(n-1, memo) + fib_v2(n-2, memo)
    return memo[n]
# 时间 O(n)，空间 O(n)（递归栈 + memo）

Step 3：DP 表（自底向上 DP）

def fib_v3(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1   # 初始值
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 状态转移
    return dp[n]
# 时间 O(n)，空间 O(n)

Step 4：空间优化（滚动数组）

def fib_v4(n):
    if n <= 1: return n
    a, b = 0, 1   # 只保存前两个状态
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
# 时间 O(n)，空间 O(1)  ← 最优

经典 DP 问题详解

爬楼梯（1D DP 入门）

每次可以爬 1 或 2 级台阶，n 级台阶共有多少种爬法？

def climb_stairs(n: int) -> int:
    # 状态：dp[i] = 爬到第 i 级有多少种方法
    # 转移：dp[i] = dp[i-1] + dp[i-2]（最后一步走1级或2级）
    # 初始：dp[1]=1, dp[2]=2
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b
# 本质是 Fibonacci 数列，实际上 climb_stairs(n) = fib(n+1)

0/1 背包问题（2D DP）

有 n 件物品，每件有重量 w[i] 和价值 v[i]。背包容量为 W，每件物品只能取一次，求最大价值。

def knapsack_01(weights, values, W):
    n = len(weights)
    # dp[i][j] = 前 i 件物品，容量 j 的背包能装的最大价值
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(W + 1):
            # 不选第 i 件物品
            dp[i][j] = dp[i-1][j]
            # 选第 i 件物品（前提：放得下）
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i][j],
                               dp[i-1][j - weights[i-1]] + values[i-1])

    return dp[n][W]

# 空间优化为 1D（从右向左更新，防止覆盖）
def knapsack_01_1d(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for j in range(W, weights[i] - 1, -1):  # 从右向左！
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

时间O(nW) 空间（优化后）O(W)

最长公共子序列（LCS）

求两个字符串 s1 和 s2 的最长公共子序列（子序列可以不连续）。

def lcs(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    # dp[i][j] = s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # 字符相等，LCS+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 取两方向最大

    return dp[m][n]

最长递增子序列（LIS）

# 解法一：O(n²) DP
def lis_n2(nums: list) -> int:
    n = len(nums)
    dp = [1] * n   # dp[i] = 以 nums[i] 结尾的 LIS 长度
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 解法二：O(n log n) 贪心 + 二分查找
import bisect

def lis_nlogn(nums: list) -> int:
    tails = []  # tails[i] = 长度为 i+1 的所有递增子序列中，最小的尾元素
    for x in nums:
        pos = bisect.bisect_left(tails, x)  # 找 x 应插入的位置
        if pos == len(tails):
            tails.append(x)   # x 比所有尾元素大，LIS 延长
        else:
            tails[pos] = x    # 替换，维护最小尾元素
    return len(tails)

编辑距离

将字符串 word1 转化为 word2 最少需要几步操作（插入、删除、替换各算一步）。

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # dp[i][j] = word1[0..i-1] → word2[0..j-1] 的最少操作数
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化：空字符串到长度为 j 的字符串需要 j 次插入
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]     # 字符相同，无需操作
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],     # 删除 word1[i]
                    dp[i][j-1],     # 插入 word2[j]
                    dp[i-1][j-1]   # 替换
                )
    return dp[m][n]

最小路径和（矩阵路径）

def min_path_sum(grid) -> int:
    m, n = len(grid), len(grid[0])
    # 原地修改作为 DP 表
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            elif i == 0:
                grid[i][j] += grid[i][j-1]       # 只能从左来
            elif j == 0:
                grid[i][j] += grid[i-1][j]       # 只能从上来
            else:
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[m-1][n-1]

区间 DP 简介

区间 DP 的状态定义在区间 [i, j] 上，通常枚举分割点 k。

# 矩阵连乘：求 n 个矩阵相乘的最小标量乘法次数
def matrix_chain(dims):
    """dims[i-1] × dims[i] 是第 i 个矩阵的维度"""
    n = len(dims) - 1   # n 个矩阵
    dp = [[0] * n for _ in range(n)]

    # 枚举子链长度
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n-1]