动态规划入门与基础模型

简介

动态规划（Dynamic Programming，简称DP）是解决一类具有重叠子问题和最优子结构特性的复杂问题的强大算法范式。它并非指在程序运行时动态地改变代码，而是一种通过将原问题分解为相对简单的子问题，并系统地存储子问题的解来避免重复计算，从而高效获得最终解的算法思想。与暴力递归相比，动态规划通过空间换时间，将指数级的时间复杂度优化为多项式级别，是算法竞赛和面试中的核心考点。

本章将系统性地介绍动态规划的基础。我们将从理解其两大核心思想——最优子结构和重叠子问题——入手，掌握其标准化的解题步骤。随后，我们将通过一系列由浅入深的经典模型进行实战演练，包括一维模型（如斐波那契数列、爬楼梯、打家劫舍）和二维模型（如最长公共子序列、编辑距离）。掌握这些基础模型是通往更复杂的背包问题、区间DP、状态压缩DP等高级动态规划领域的必经之路。

核心概念

动态规划的有效性建立在两个关键概念之上：最优子结构和重叠子问题。

最优子结构是指一个问题的最优解包含其子问题的最优解。也就是说，我们可以通过组合子问题的最优解来构造原问题的最优解。例如，在求从A点到B点的最短路径时，若途径C点，那么这条最短路径必然由A到C的最短路径和C到B的最短路径组成。这个性质使得我们可以放心地求解子问题，并相信它们的解对父问题是有贡献的。

重叠子问题是指在递归求解问题的过程中，相同的子问题会被反复计算多次。例如，在递归计算斐波那契数列F(5)时，F(3)会被计算多次。动态规划通过记忆化（Memoization，自顶向下）或制表法（Tabulation，自底向上）将子问题的解存储在一个表格（通常是数组或字典）中，当再次需要时直接查表，从而消除重复计算。

标准的动态规划解题包含四个清晰步骤： 1. 定义状态：明确dp数组（或其它数据结构）以及每个下标的含义。这是最关键的一步，状态定义决定了问题的分解方式。 2. 推导状态转移方程：找出状态之间的关系式，即如何从已知状态推导出未知状态。这是动态规划的核心逻辑。 3. 确定初始与边界条件：确定dp数组的起点值，以及处理边界情况（如数组越界）的方法。 4. 确定计算顺序与输出：决定状态的计算方向（自顶向下还是自底向上），并明确最终答案存储在哪个状态中。

下面的流程图概括了动态规划从问题识别到求解的完整思维过程：

实战示例

经典一维DP模型

1. 斐波那契数列

这是理解重叠子问题最直观的例子。状态定义很直接：dp[i]表示第i个斐波那契数的值。

def fibonacci(n):
"""
计算第n个斐波那契数（n从0开始）。
状态定义：dp[i] 表示第i个斐波那契数的值。
转移方程：dp[i] = dp[i-1] + dp[i-2]。
初始条件：dp[0] = 0, dp[1] = 1。
"""
if n < 2:
return n
dp = [0] * (n + 1)  # 创建dp表
dp[0], dp[1] = 0, 1  # 初始化
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]  # 状态转移
return dp[n]
# 测试
print(fibonacci(10))  # 输出：55

2. 爬楼梯问题（LeetCode 70）

问题：每次可以爬1或2个台阶，爬到第n阶有多少种不同的方法？ 状态定义：dp[i]表示爬到第i阶台阶的方法总数。

def climb_stairs(n):
"""
爬楼梯问题。
状态定义：dp[i] 表示到达第i阶的方法数。
转移方程：要到达第i阶，可以从第i-1阶爬1步上来，或从第i-2阶爬2步上来。故 dp[i] = dp[i-1] + dp[i-2]。
初始条件：dp[0] = 1 (理解为起点的一种方法), dp[1] = 1。
"""
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 测试
print(climb_stairs(5))  # 输出：8

3. 打家劫舍（LeetCode 198）

问题：不能抢劫相邻的房屋，求能盗取的最大金额。这是最优子结构的典型应用。 状态定义：dp[i]表示考虑前i个房屋（下标0到i-1）时，能偷窃到的最高金额。

def rob(nums):
"""
打家劫舍问题。
状态定义：dp[i] 表示考虑前i个房子时能获得的最大金额。
转移方程：对于第i个房子（下标i-1），有两种选择：
1. 不偷它，则金额等于 dp[i-1]。
2. 偷它，则不能偷前一个，金额等于 dp[i-2] + nums[i-1]。
取两者最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。
初始条件：dp[0] = 0 (没有房子)，dp[1] = nums[0] (只有第一个房子)。
"""
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * (n + 1)
dp[0], dp[1] = 0, nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n]
# 测试
print(rob([2, 7, 9, 3, 1]))  # 输出：12 (偷第1、3、5个房子：2+9+1)

经典二维DP模型

4. 最长公共子序列（LeetCode 1143）

问题：给定两个字符串，返回它们的最长公共子序列的长度。子序列不要求连续。 状态定义：dp[i][j]表示文本串text1的前i个字符和text2的前j个字符的最长公共子序列长度。

def longest_common_subsequence(text1, text2):
"""
最长公共子序列(LCS)。
状态定义：dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的LCS长度。
转移方程：
if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始条件：dp[0][j] = 0, dp[i][0] = 0。
"""
m, n = len(text1), len(text2)
# 创建 (m+1) x (n+1) 的dp表，多出一行一列用于处理空串情况
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
# 字符匹配，长度加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]
# 测试
text1 = "abcde"
text2 = "ace"
print(longest_common_subsequence(text1, text2))  # 输出：3 ("ace")

5. 编辑距离（LeetCode 72）

问题：计算将单词word1转换成word2所需的最少操作数（插入、删除、替换一个字符）。 状态定义：dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小编辑距离。

def min_distance(word1, word2):
"""
编辑距离问题。
状态定义：dp[i][j] 表示将 word1[0:i] 转换为 word2[0:j] 的最小操作数。
转移方程：
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,    # 删除 word1[i-1]
dp[i][j-1] + 1,    # 在word1插入 word2[j-1]
dp[i-1][j-1] + 1   # 替换 word1[i-1] 为 word2[j-1]
)
初始条件：dp[i][0] = i (删除i次), dp[0][j] = j (插入j次)。
"""
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],    # 删除
dp[i][j - 1],    # 插入
dp[i - 1][j - 1] # 替换
) + 1
return dp[m][n]
# 测试
word1 = "horse"
word2 = "ros"
print(min_distance(word1, word2))  # 输出：3

对比分析

不同的动态规划模型适用于不同类型的问题。理解它们的特点有助于快速识别和套用模型。

最佳实践

1. 从暴力递归思考：如果对状态转移没有头绪，先尝试写出暴力递归解法。这能帮助你理清问题的子结构。然后观察递归树中是否存在重叠子问题，这往往是动态规划的切入点。
2. 明确状态定义是第一要务：dp数组下标的含义必须清晰无误。一个好的状态定义应该能够包含问题的所有信息，并且能够通过转移方程从其他状态推导出来。可以尝试用一句完整的话来描述dp[i]或dp[i][j]。
3. 重视初始化和边界处理：不正确的初始化是动态规划错误的常见原因。务必仔细考虑dp[0]、dp[0][0]等初始状态的含义。对于可能越界的访问（如dp[i-2]当i=1时），要在循环中判断或通过增加数组维度来规避。
4. 尝试空间优化：许多一维DP（如斐波那契、打家劫舍）的状态转移只依赖于前两个状态，因此可以将O(n)的空间复杂度优化为O(1)，只使用几个变量滚动更新。二维DP有时也可以优化为一维。但在初学阶段，应先写出完整的、易理解的版本，再考虑优化。
5. 画出DP表辅助调试：对于复杂的二维DP，在纸上手动模拟填充dp表是理解状态转移和发现逻辑错误非常有效的方法。特别是对于编辑距离这类问题，画表能直观展示操作过程。

小结

动态规划是一种通过分解问题、存储子问题解来高效求解具有最优子结构和重叠子问题特性的算法思想。掌握其核心在于遵循定义状态、推导方程、确定初始化、确定顺序的四步法。通过斐波那契、爬楼梯等一维模型，我们学会了处理线性递推关系；通过最长公共子序列和编辑距离等二维模型，我们掌握了处理双序列比对问题的通用框架。这些基础模型是构建更复杂动态规划解决方案的基石。理解状态定义的内涵和转移方程的逻辑，并通过大量练习培养直觉，是精通动态规划的不二法门。

下一节：动态规划进阶：背包与区间问题