介绍
把大问题拆成 重叠子问题（重复的小问题），先算小问题，使用数组存储子问题结果，再一步步算出大问题。
与贪心、分治法类似
审题技巧
如果提到 最优子结构 和 递归式 字样，说明是 动态规划法
实现方式
自顶向下
自底向上
实现方式一：自顶向下
特点：用到 递归
如：斐波那契
f(100) + f(99) + f(98) + f(97) + ... + f(1)
注意：自顶向下，到底后，还要向上执行，所以时间复杂度比 自底向上 大
时间复杂度
O(2^n)
实现方式二：自底向上
特点：用到 循环 + 数组（一维、二维…）
如：计算二维数组的某种结果，需要用到双重循环
arr[0][0]
arr[0][1]
arr[0][2]
....
arr[m][n]
时间复杂度
O(n^a) ( a：几重循环就是几)
经典问题
- 斐波那契数列
- 矩阵乘法
- 0-1背包问题（每个物品只有两种选择：装入背包或不装入背包）
- LCS最长公共子序列
斐波那契数列
自顶向下
# 自顶向下（记忆化递归）计算斐波那契
def fib_top_down(n, memo=None):
# 初始化备忘录（第一次调用时创建）
if memo is None:
memo = {} # 用字典存已经算过的结果，key是n，value是F(n)
# 1. 递归终止条件（最小子问题）
if n == 0:
return 0
if n == 1:
return 1
# 2. 先查备忘录：有就直接返回，不重复算
if n in memo:
return memo[n]
# 3. 没有就递归计算，并存入备忘录
res = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
memo[n] = res # 存结果，下次直接用
return res
# 测试：计算第5个斐波那契数（结果应为5）
print(fib_top_down(5)) # 输出：5
# 测试：计算第10个斐波那契数（结果应为55）
print(fib_top_down(10)) # 输出：55
自底向上
# 动态规划计算斐波那契
def fib_dp(n):
# 边界条件
if n == 0:
return 0
if n == 1:
return 1
# 用数组存储子问题的解（避免重复计算）
dp = [0] * (n+1)
dp[0] = 0
dp[1] = 1
# 自底向上计算：先算小问题（F(2)），再算大问题（F(5)）
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 计算F(5)
print(fib_dp(5)) # 输出：5
特点：每次算法都存起来
分治法：每次都重复计算，不会存起来
案例-最大子段和（必考！）
问题： 给一串整数，找连续一段和最大。
DP 公式（背下来）：
dp[i] = max( arr[i], dp[i-1] + arr[i] )
意思：
- 要么自己重新开始一段
- 要么跟前面连起来
时间复杂度：O(n)
案例-最长公共子序列 LCS（高频）
问题： 两个字符串，找最长的、顺序一样的公共子序列。
比如：
- abcde
- ace
→ 最长公共子序列是 ace，长度 3
DP 思路：
- 建二维数组
- 字符相同：
dp[i][j] = dp[i-1][j-1] + 1 - 不同：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
时间复杂度：O(n*m)