一句话总结
动态规划核心：将大问题分解为重叠子问题，用数组/矩阵存储中间结果避免重复计算。解题五步法：1）定义 dp[i] 含义 → 2）推导递推公式 → 3）初始化 dp 数组 → 4）确定遍历顺序 → 5）举例推导验证。背包问题：0-1 背包（每个物品用一次，倒序遍历），完全背包（每个物品无限次，正序遍历）。
初级理解
DP 五步法 — 以斐波那契为例
# 斐波那契数列：F(n) = F(n-1) + F(n-2)
# 1. 定义 dp[i]：第 i 个斐波那契数
# 2. 递推公式：dp[i] = dp[i-1] + dp[i-2]
# 3. 初始化：dp[0] = 0, dp[1] = 1
# 4. 遍历顺序：从 2 到 n
# 5. 举例：n=5 → 0,1,1,2,3,5
def fib(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]
# 空间优化（滚动数组）
def fib_optimized(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
爬楼梯（LeetCode 70）
# 每次爬 1 或 2 阶，到第 n 阶有多少种方法
# dp[i]：爬到第 i 阶的方法数
# dp[i] = dp[i-1] + dp[i-2]（最后一步爬 1 阶或 2 阶）
# dp[0]=1, dp[1]=1
def climb_stairs(n):
if n <= 2: return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
一句话总结：DP 五步法：定义 → 递推 → 初始化 → 遍历 → 验证。
中级深入
0-1 背包问题
# 问题：N 个物品，重量 weight[i]，价值 value[i]
# 背包容量 W，求最大价值（每个物品最多用一次）
# dp[j]：容量 j 的背包最大价值
# dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
# 遍历顺序：物品正序，容量倒序（防止重复使用）
def knapsack_01(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]
# 为什么倒序？防止同一物品被多次使用
# 正序：dp[j-weight[i]] 可能已经包含了物品 i → 完全背包
# 倒序：dp[j-weight[i]] 一定不包含物品 i → 0-1 背包
完全背包（零钱兑换 LeetCode 322）
# 零钱兑换：最少硬币数凑成 amount
# dp[i]：凑成金额 i 的最少硬币数
# dp[i] = min(dp[i], dp[i-coin] + 1)
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins: # 物品
for i in range(coin, amount + 1): # 容量正序（完全背包）
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
中级要点：0-1 背包容量倒序，完全背包容量正序；dp[j] = max(dp[j], dp[j-w]+v)。
高级拓展
最长递增子序列（LeetCode 300）
# dp[i]：以 nums[i] 结尾的最长递增子序列长度
# dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]
# O(n^2)
def length_of_lis(nums):
dp = [1] * len(nums)
for i in range(len(nums)):
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 = []
for num in nums:
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
tails.append(num)
else:
tails[idx] = num
return len(tails)
编辑距离（LeetCode 72）
# word1 转 word2 的最少操作数（插入/删除/替换）
# dp[i][j]：word1[:i] 转 word2[:j] 的最少操作数
# word1[i-1] == word2[j-1] → dp[i][j] = dp[i-1][j-1]
# word1[i-1] != word2[j-1] → dp[i][j] = 1 + min(
# dp[i-1][j], # 删除 word1[i-1]
# dp[i][j-1], # 插入 word2[j-1]
# dp[i-1][j-1] # 替换
# )
def min_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] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
实战场景
场景：最长公共子序列（LeetCode 1143）
# dp[i][j]：text1[:i] 和 text2[:j] 的最长公共子序列
# text1[i-1] == text2[j-1] → dp[i][j] = dp[i-1][j-1] + 1
# text1[i-1] != text2[j-1] → dp[i][j] = max(dp[i-1][j], dp[i][j-1])
def longest_common_subsequence(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]
面试模拟
面试官：动态规划的解题步骤？
你：五步法：1）明确 dp[i] 或 dp[i][j] 的含义；2）推导递推公式（状态转移方程）；3）初始化 dp 数组（base case）；4）确定遍历顺序（正序/倒序，先物品还是先容量）；5）举例推导验证。最关键的是找到递推公式。
面试官：0-1 背包和完全背包有什么区别？
你：0-1 背包每个物品只能用一次，容量倒序遍历（防止重复使用）；完全背包每个物品无限次，容量正序遍历。递推公式相同：dp[j] = max(dp[j], dp[j-w]+v)。