核心要点
五步法：定义状态 dp[i] 的含义 → 推导转移方程 → 初始化边界 → 确定遍历顺序 → 滚动数组优化空间
复杂度：状态数 × 单状态转移代价，常见 O(n) 或 O(n·m)
易错点：状态定义不清导致转移写错；遍历顺序与依赖关系不一致；边界 dp[0] 未初始化
标准回答
动态规划适用于具有「最优子结构」和「重叠子问题」的题目，核心是把大问题拆成可复用的子问题并缓存结果。解题套路固定为五步：先明确 dp 数组每个下标的含义，再根据当前状态如何由更小状态推导写出转移方程，然后初始化边界值，接着按依赖方向确定遍历顺序，最后视情况用滚动变量降低空间。下面以经典的爬楼梯（每次走 1 或 2 阶，问到第 n 阶有几种走法）和最长公共子序列两个例子说明：
python
def climb_stairs(n: int) -> int:
# 状态 dp[i]：到达第 i 阶的方法数
# 转移方程：dp[i] = dp[i-1] + dp[i-2]（最后一步走 1 或 2 阶）
# 边界：dp[0]=1（原地一种）, dp[1]=1
if n <= 1:
return 1
prev2, prev1 = 1, 1 # 用两个变量做滚动数组，省空间
for _ in range(2, n + 1): # 遍历顺序：从小到大，因为 dp[i] 依赖更小的下标
prev2, prev1 = prev1, prev1 + prev2
return prev1
def longest_common_subsequence(a: str, b: str) -> int:
# 状态 dp[i][j]：a 前 i 个字符与 b 前 j 个字符的最长公共子序列长度
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)] # 边界整行整列为 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[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]
if __name__ == '__main__':
print(climb_stairs(5)) # 8
print(longest_common_subsequence('abcde', 'ace')) # 3常见误区
⚠️ 常见踩坑
把「子序列」误当成「子串」（子序列不要求连续）；遍历顺序与状态依赖方向相反，导致用到尚未计算的值。
追问
追问 1：爬楼梯和 LCS 的时间空间复杂度分别是多少？
爬楼梯时间 O(n)、空间 O(1)（滚动变量）。LCS 时间 O(m·n)、空间 O(m·n)，可用一维滚动数组优化到 O(min(m,n))。
追问 2：如何判断一道题能不能用动态规划？
看是否同时具备最优子结构（大问题最优解由子问题最优解组成）和重叠子问题（递归时同一子问题被反复计算）。若子问题不重叠，分治即可；若有后效性（当前决策影响未来状态的合法性），需重新设计状态消除后效性。
延伸学习
与本题相关的知识库文章、术语、工具与行业资讯。