动态规划

• 重叠子问题（Overlapping Subproblems） 同一个子问题会被重复计算多次。例如 fib(5) = fib(4) + fib(3)，而 fib(4) = fib(3) + fib(2)，fib(3) 被计算了两次。DP 将子问题的解存储起来（记忆化），每个子问题只解一次。
• 最优子结构（Optimal Substructure） 问题的最优解包含子问题的最优解。即可以从子问题的最优解推导出原问题的最优解。例如：从 A 到 C 的最短路径，经过 B，则 A→B 和 B→C 分别也是各自的最短路径。
• 状态（State） 用于描述子问题的参数组合，是 DP 表的"索引"。状态定义是 DP 的核心——状态必须包含做决策所需的全部信息。一维 dp[i]、二维 dp[i][j]，甚至状压 dp[mask] 都是状态的不同形式。
• 状态转移方程（Transition Equation） 描述 dp[i] 如何由更小的子状态推导而来的公式。推导技巧："最后一步"分析——考虑当前状态的最后一个决策是什么，枚举所有可能的最后决策，取最优。
• 记忆化搜索（Memoization） 自顶向下的 DP：用递归实现，第一次计算某子问题时将结果存入哈希表/数组，后续直接查表。写起来接近暴力递归，但时间复杂度与迭代 DP 相同。适合状态空间稀疏或边界复杂的情况。
• 滚动数组（Rolling Array） 空间优化技术。当 dp[i] 只依赖 dp[i-1]（或少数前几行）时，可以只保留前几行，将 O(n) 空间降为 O(1)（或 O(行数)）。0/1 背包问题将 O(nW) 空间降为 O(W) 的核心技巧。

什么是动态规划

动态规划（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]

DP 类型速查

类型	典型题	状态维度	代表转移
线性 DP	爬楼梯、打家劫舍	dp[i]	dp[i] = dp[i-1] + dp[i-2]
背包 DP	0/1背包、完全背包	dp[i][j]	dp[i][j] = max(不选, 选)
字符串 DP	LCS、编辑距离	dp[i][j]	字符相等/不等分支
区间 DP	矩阵连乘、戳气球	dp[i][j]	枚举分割点 k
树形 DP	打家劫舍 III	dp[node][选/不选]	子树状态合并
状压 DP	TSP、最小覆盖	dp[mask]	枚举子集或加入新元素

完全背包（每件可取无限次）

def knapsack_complete(weights, values, W):
    """完全背包：每件物品可以取任意多次"""
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        # 关键区别：从左向右更新（允许重复选取同一物品）
        for j in range(weights[i], W + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

# 零钱兑换（完全背包变体）：最少硬币数
def coin_change(coins: list, amount: int) -> int:
    # dp[i] = 凑出金额 i 所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # 凑出 0 元需要 0 枚
    for coin in coins:
        for j in range(coin, amount + 1):  # 完全背包：从左往右
            dp[j] = min(dp[j], dp[j - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1