动态规划从入门到精通 — 核心思想与经典问题

动态规划（Dynamic Programming，简称 DP）是算法领域中最强大也最令人望而生畏的技术之一。它的名字听起来高深莫测——实际上 Richard Bellman 在 20 世纪 50 年代提出这个名字时，故意选了一个”听起来很厉害”的词来争取研究经费。然而，动态规划的核心思想却极其朴素：将复杂问题分解为重叠的子问题，通过存储子问题的解来避免重复计算。

许多程序员觉得 DP 难，主要原因有三：一是不知道何时该用 DP，二是不知道如何定义状态，三是不知道如何推导状态转移方程。本文将从 DP 的核心理论出发，通过五个由浅入深的经典问题，帮助你建立完整的 DP 思维框架。

DP 的三大要素

一个问题能用动态规划求解，必须同时满足以下三个条件：

1. 最优子结构（Optimal Substructure）

问题的最优解包含其子问题的最优解。换言之，我们可以通过组合子问题的最优解来构造原问题的最优解。例如，最短路径问题中，从 A 到 C 的最短路径如果经过 B，那么 A→B 和 B→C 分别也是最短路径。

2. 重叠子问题（Overlapping Subproblems）

在递归求解过程中，相同的子问题会被多次计算。这正是 DP 相对于暴力递归的优势所在——通过记录已计算的结果，将指数级别的时间复杂度降低到多项式级别。以斐波那契数列为例，递归计算 F(n) 时，F(2) 会被计算指数次，而 DP 只计算一次。

3. 无后效性（No Aftereffect）

某阶段的状态一旦确定，就不会受此后决策的影响。也就是说，未来的决策不会改变过去的状态。这要求我们在定义状态时必须包含足够的信息，使得状态转移只依赖于当前状态和决策，而非历史路径。

DP 解题四步法

无论多么复杂的 DP 问题，都可以遵循以下四个步骤来求解：

第一步：定义状态。 明确 dp[i]（或 dp[i][j] 等）代表什么含义。好的状态定义是解题的关键。

第二步：推导状态转移方程。 找到 dp[i] 与 dp[i-1]（或其他子状态）之间的关系。这通常是最困难的一步。

第三步：确定初始条件（边界条件）。 确定最小规模子问题的解，即递推的起点。

第四步：确定遍历顺序。 确保在计算 dp[i] 时，其依赖的所有子状态都已经计算完毕。

经典问题一：爬楼梯（入门）

问题描述

假设你正在爬一个有 n 阶的楼梯，每次可以爬 1 阶或 2 阶。问有多少种不同的方法到达楼顶？

思路分析

到达第 n 阶楼梯，要么从第 n-1 阶爬 1 步上来，要么从第 n-2 阶爬 2 步上来。因此第 n 阶的方法数等于到达第 n-1 阶和第 n-2 阶的方法数之和。

状态定义与转移方程

状态定义：dp[i] 表示到达第 i 阶楼梯的方法数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
初始条件：dp[0] = 1（站在地面，一种方式），dp[1] = 1（爬一阶，一种方式）
遍历顺序：从小到大

代码实现

def climb_stairs(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# 空间优化版本（只需两个变量）
def climb_stairs_optimized(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

复杂度分析： 时间 O(n)，空间 O(1)（优化版）。

这个问题本质上就是斐波那契数列，虽然简单，但完整展示了 DP 的四步解题法。

经典问题二：0-1 背包问题（核心）

问题描述

有 n 个物品和一个容量为 W 的背包，第 i 个物品的重量为 weight[i]，价值为 value[i]。每个物品只能选择放或不放（0-1 选择），求在不超过背包容量的前提下能获得的最大价值。

思路分析

对于每个物品，我们有两个选择：放入背包或不放入。这是一个组合优化问题，暴力枚举需要 O(2^n) 时间，而 DP 可以在 O(nW) 时间内求解。

状态定义与转移方程

状态定义：dp[i][j] 表示前 i 个物品中，背包容量为 j 时能获得的最大价值
状态转移方程：
- 不选第 i 个物品：dp[i][j] = dp[i-1][j]
- 选第 i 个物品（前提 j >= weight[i]）：dp[i][j] = dp[i-1][j-weight[i]] + value[i]
- 取两者最大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
初始条件：dp[0][j] = 0（没有物品可选，价值为 0）

代码实现

def knapsack_01(weights, values, capacity):
    n = len(weights)
    # dp[i][j]: 前i个物品、容量j时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(capacity + 1):
            dp[i][j] = dp[i - 1][j]  # 不选第i个物品
            if j >= weights[i - 1]:   # 可以选第i个物品
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

# 空间优化：一维数组（逆序遍历保证每个物品只被选一次）
def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for j in range(capacity, weights[i] - 1, -1):  # 逆序遍历！
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[capacity]

复杂度分析： 时间 O(nW)，空间 O(W)（优化版）。

注意一维优化版中内层循环必须逆序遍历，这是因为我们需要使用的是”上一行”的值。如果正序遍历，dp[j - weights[i]] 可能已经被当前行更新过，相当于物品被重复选取（这就变成了完全背包问题）。

经典问题三：最长公共子序列 LCS

问题描述

给定两个字符串 s1 和 s2，找出它们的最长公共子序列的长度。子序列不要求连续，但要求保持原始顺序。

思路分析

比较两个字符串当前位置的字符：如果相同，则 LCS 长度加 1；如果不同，则分别尝试跳过一个字符串的当前字符，取较大值。

状态定义与转移方程

状态定义：dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的 LCS 长度
状态转移方程：
- 若 s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
- 若 s1[i-1] != s2[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始条件：dp[0][j] = dp[i][0] = 0

代码实现

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    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
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# 示例
print(longest_common_subsequence("abcde", "ace"))  # 输出: 3 ("ace")

复杂度分析： 时间 O(mn)，空间 O(mn)，可优化至 O(min(m,n))。

经典问题四：编辑距离（Levenshtein Distance）

问题描述

给定两个字符串 word1 和 word2，求将 word1 转换为 word2 所需的最少操作数。允许的操作有：插入一个字符、删除一个字符、替换一个字符。

思路分析

编辑距离是自然语言处理、拼写检查、DNA 序列比对等领域的基础算法。我们可以定义一个二维 DP 表，其中每个单元格表示两个字符串前缀之间的编辑距离。

状态定义与转移方程

状态定义：dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数
状态转移方程：
- 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（无需操作）
- 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  - dp[i-1][j] + 1：删除 word1 的第 i 个字符
  - dp[i][j-1] + 1：在 word1 中插入 word2 的第 j 个字符
  - dp[i-1][j-1] + 1：替换 word1 的第 i 个字符
初始条件：dp[i][0] = i，dp[0][j] = j

代码实现

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始条件
    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] = min(
                    dp[i - 1][j] + 1,      # 删除
                    dp[i][j - 1] + 1,      # 插入
                    dp[i - 1][j - 1] + 1   # 替换
                )

    return dp[m][n]

# 示例
print(edit_distance("kitten", "sitting"))  # 输出: 3

复杂度分析： 时间 O(mn)，空间 O(mn)，可用滚动数组优化至 O(min(m,n))。

经典问题五：最长递增子序列 LIS

问题描述

给定一个整数数组，找出其中最长严格递增子序列的长度。

思路分析

LIS 问题有多种解法，从 O(n²) 的基本 DP 到 O(n log n) 的贪心+二分优化。

状态定义与转移方程

方法一：O(n²) DP

状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
状态转移方程：dp[i] = max(dp[j] + 1) 其中 0 <= j < i 且 nums[j] < nums[i]
初始条件：dp[i] = 1（每个元素自身构成长度为 1 的子序列）

代码实现

# 方法一：O(n²) DP
def length_of_lis(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n

    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 length_of_lis_optimized(nums):
    # tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

# 示例
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出: 4 ([2,3,7,101])

复杂度分析： 方法一时间 O(n²)，空间 O(n)；方法二时间 O(n log n)，空间 O(n)。

方法二的核心思想是贪心：为了让递增子序列尽可能长，我们希望每个位置的末尾元素尽可能小。tails 数组始终保持有序，因此可以用二分查找高效定位插入位置。

DP 优化技巧

滚动数组

当状态转移只涉及相邻两行时（如 dp[i] 只依赖 dp[i-1]），可以用两个一维数组交替使用，将空间从 O(mn) 降至 O(n)：

# 以 LCS 为例的滚动数组优化
def lcs_rolling(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)

    return prev[n]

一维空间压缩

在 0-1 背包中我们已经看到，通过逆序遍历可以在一维数组上原地更新，避免使用二维数组。这种技巧的关键在于理解遍历顺序对依赖关系的影响。

记忆化搜索 vs 自底向上

DP 有两种实现方式：

特性	记忆化搜索（自顶向下）	表格法（自底向上）
实现方式	递归 + 哈希表/数组缓存	迭代 + 数组填表
思维方式	自然递归思维，更直观	需要想清楚遍历顺序
计算量	只计算需要的子问题	计算所有子问题
空间开销	递归栈 + 缓存	仅数组
常数因子	递归调用开销较大	循环开销小
适用场景	状态空间稀疏、复杂状态	状态空间密集、规则

# 记忆化搜索示例（爬楼梯）
from functools import lru_cache

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

对于大多数竞赛题目和实际应用，自底向上的表格法更常用，因为没有递归栈溢出的风险且常数因子更小。而记忆化搜索在状态空间不规则或状态定义复杂时更具优势。

何时使用动态规划

判断一个问题是否适合 DP，可以从以下角度思考：

问题是否要求最优值（最大/最小/最长/最短/方案数）？如果是，可能适合 DP。
问题是否具有选择性（选或不选、走左还是走右）？如果每一步都有选择，可能适合 DP。
暴力解法是否有大量重复计算？画出递归树，观察是否存在重复子问题。
能否定义清晰的状态？如果一个子问题的解可以用有限个参数唯一确定，就可以用 DP。
贪心是否可行？如果局部最优不能导出全局最优，而 DP 可以通过枚举所有选择来保证全局最优。

常见的 DP 问题类型包括：线性 DP（爬楼梯、LIS）、区间 DP（矩阵链乘法、戳气球）、背包 DP（0-1 背包、完全背包）、树形 DP（二叉树中的最大路径和）、状态压缩 DP（旅行商问题）、数位 DP（统计满足条件的数字个数）等。

总结

动态规划的精髓在于用空间换时间，通过存储子问题的解来避免重复计算。掌握 DP 需要大量练习，但核心方法论是统一的：

想清楚状态是什么——这是 DP 最关键的一步
推导状态转移方程——从最后一步反推
明确初始条件和遍历顺序
考虑空间优化的可能性

从爬楼梯到背包问题，从 LCS 到编辑距离，每一个经典问题都是一种思维模式的训练。当你做够了足够多的题目，你会发现新问题往往是经典模型的变形或组合。动态规划不是天赋，而是可以通过系统训练习得的技能。