动态规划（Dynamic Programming，简称DP）是算法学习中最重要也最具挑战性的思想之一。它通过将复杂问题分解为相互重叠的子问题，并存储子问题的解来避免重复计算，从而大幅提升效率。本文将通过两个经典例题，带你掌握动态规划的核心思路。
一、动态规划的本质
动态规划的核心可以用一句话概括：“记住你之前算过的结果，避免重复劳动。”
一个问题能用动态规划解决，通常需要满足两个条件：
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：不同的决策路径会重复遇到相同的子问题
二、经典例题一：0-1背包问题
问题描述
给定n个物品，每个物品有重量weight[i]和价值value[i]。背包容量为W，每个物品只能选一次。求能装入背包的最大价值。
状态定义
设dp[i][j]表示前i个物品，在背包容量为j时能获得的最大价值。
状态转移方程
if j >= weight[i]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
else:
dp[i][j] = dp[i-1][j]
空间优化
观察到dp[i][j]只依赖于上一行的数据，可以将二维数组优化为一维，并采用倒序遍历：
# 一维DP版本
for i in range(n):
for j in range(W, weight[i]-1, -1):
dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
三、经典例题二：最长公共子序列（LCS）
问题描述
给定两个字符串text1和text2，返回它们最长公共子序列的长度。子序列不要求连续，但要求相对顺序一致。
状态定义
设dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列长度。
状态转移方程
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])
Python实现
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
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]:
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]
四、动态规划的解题框架
面对一道动态规划题目，可以按照以下步骤思考：
- 明确状态：用什么变量描述子问题的解？
- 定义dp数组：dp[i]或dp[i][j]代表什么含义？
- 寻找转移方程：当前状态如何从之前的状态推导而来？
- 确定初始条件和边界：哪些状态是已知的？
- 考虑优化：能否降低时间或空间复杂度？
五、复杂度对比
| 问题 | 时间复杂度 | 空间复杂度 | 优化后空间 |
|---|---|---|---|
| 0-1背包 | O(n×W) | O(n×W) | O(W) |
| 完全背包 | O(n×W) | O(n×W) | O(W) |
| 最长公共子序列 | O(m×n) | O(m×n) | O(min(m,n)) |
结语
动态规划是算法面试中的高频考点，也是解决实际优化问题的利器。掌握0-1背包和最长公共子序列这两个经典模型，你就已经迈入了动态规划的大门。后续可以继续挑战最长递增子序列、编辑距离、股票买卖问题等进阶题目，逐步建立起对DP的直觉和信心。
