第 14 课：动态规划（DP）—— 算法思想的巅峰，面试的终极分水岭
这是所有算法中最难也最重要的部分，也是区分普通程序员和优秀程序员的分水岭。很多人觉得动态规划难，是因为没有掌握正确的思维方式。其实，90% 的动态规划题都有固定的解题模板，只要你掌握了这个模板，就能轻松解决绝大多数面试题。
一、先想明白：为什么要有动态规划？
我们先看一个最简单的问题：斐波那契数列。
斐波那契数列定义：F (0)=0, F (1)=1, F (n)=F (n-1)+F (n-2)求 F (20)
暴力递归解法：
python
运行
def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2)这个解法是正确的，但时间复杂度是 O (2ⁿ)，指数级增长。当 n=40 时，计算机就需要算好几秒了。
为什么这么慢？因为存在大量的重复计算。比如计算 F (5) 需要计算 F (4) 和 F (3)，计算 F (4) 又需要计算 F (3) 和 F (2)，这样 F (3) 就被计算了两次。n 越大，重复计算的次数就越多。
动态规划的诞生，就是为了解决这个问题：用空间换时间，把已经计算过的子问题的解存储起来，避免重复计算。
二、动态规划的本质：重叠子问题 + 最优子结构
✅ 核心思想（刻在脑子里）
把一个大问题拆成若干个重叠的子问题，存储子问题的解，然后通过子问题的解推导出原问题的解。
两个必要条件（缺一不可）
- 重叠子问题：不同的子问题包含相同的更小的子问题
- 最优子结构：原问题的最优解包含其子问题的最优解
动态规划的演化过程
- 暴力递归：最直观的解法，但存在大量重复计算，时间复杂度高
- 记忆化递归（自顶向下）：用一个数组存储已经计算过的子问题的解，避免重复计算
- 动态规划（自底向上）：从最小的子问题开始，一步步往上计算，直到得到原问题的解
✅ 记住：动态规划本质上就是去掉了重复计算的暴力递归。
三、动态规划万能解题四步走（所有 DP 题通用）
这是这一课最重要的内容，必须背下来。所有动态规划题，都按照这四步来做，没有例外。
定义 dp 数组的含义
- 这是最关键的一步，也是最难的一步
- 明确
dp[i]或者dp[i][j]到底代表什么意思 - 原则：让状态转移方程尽可能简单
找出状态转移方程
- 也就是
dp[i]和dp[i-1]、dp[i-2]... 之间的关系 - 思考：要得到
dp[i]，需要哪些子问题的解？
- 也就是
初始化 dp 数组
- 明确哪些基础情况的 dp 值是已知的
- 这些是递推的起点
确定遍历顺序
- 明确应该从前往后遍历，还是从后往前遍历
- 原则：计算
dp[i]的时候，它所依赖的所有子问题的解都已经计算完毕
四、入门例题 1：斐波那契数列（用四步走拆解）
我们用上面的四步走，重新解决斐波那契数列问题。
步骤 1：定义 dp 数组的含义
dp[i]：第 i 个斐波那契数的值
步骤 2：找出状态转移方程
根据定义，dp[i] = dp[i-1] + dp[i-2]
步骤 3：初始化 dp 数组
dp[0] = 0dp[1] = 1
步骤 4：确定遍历顺序
因为dp[i]依赖于dp[i-1]和dp[i-2]，所以应该从前往后遍历，从 2 遍历到 n。
最终代码
python
运行
def fib_dp(n): """ 计算斐波那契数列的第n项（动态规划版本） 参数: n (int): 需要计算的斐波那契数列项数 返回: int: 斐波那契数列的第n项 """ if n == 0: return 0 dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] def fib_optimized(n): """ 计算斐波那契数列的第n项（空间优化版本） 参数: n (int): 需要计算的斐波那契数列项数 返回: int: 斐波那契数列的第n项 """ if n == 0: return 0 a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b # 示例测试 if __name__ == "__main__": # 示例1: 计算第0项 n1 = 0 result1_dp = fib_dp(n1) result1_opt = fib_optimized(n1) print(f"示例1: n={n1}, 动态规划结果={result1_dp}, 优化结果={result1_opt}") # 示例2: 计算第1项 n2 = 1 result2_dp = fib_dp(n2) result2_opt = fib_optimized(n2) print(f"示例2: n={n2}, 动态规划结果={result2_dp}, 优化结果={result2_opt}") # 示例3: 计算第5项 n3 = 5 result3_dp = fib_dp(n3) result3_opt = fib_optimized(n3) print(f"示例3: n={n3}, 动态规划结果={result3_dp}, 优化结果={result3_opt}") # 示例4: 计算第10项 n4 = 10 result4_dp = fib_dp(n4) result4_opt = fib_optimized(n4) print(f"示例4: n={n4}, 动态规划结果={result4_dp}, 优化结果={result4_opt}") # 示例5: 计算第20项 n5 = 20 result5_dp = fib_dp(n5) result5_opt = fib_optimized(n5) print(f"示例5: n={n5}, 动态规划结果={result5_dp}, 优化结果={result5_opt}")时间复杂度：O(n)空间复杂度：O(n)
空间优化
因为dp[i]只依赖于dp[i-1]和dp[i-2]，所以我们不需要存储整个 dp 数组，只需要存储前两个值即可。
python
运行
def fib(n): if n == 0: return 0 a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b空间复杂度优化到 O (1)
五、入门例题 2：爬楼梯（和斐波那契一模一样）
题目：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬 1 个或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
用四步走拆解
- 定义 dp 数组：
dp[i]表示爬到第 i 阶楼梯的方法数 - 状态转移方程：爬到第 i 阶的方法数 = 爬到第 i-1 阶的方法数（再爬 1 阶） + 爬到第 i-2 阶的方法数（再爬 2 阶）即：
dp[i] = dp[i-1] + dp[i-2] - 初始化：
dp[1] = 1（只有 1 阶，只有 1 种方法），dp[2] = 2（1+1 或 2） - 遍历顺序：从前往后遍历，从 3 遍历到 n
代码
python
运行
def climbStairs(n): """ 计算爬到n阶楼梯的方法数 参数: n (int): 楼梯的阶数 返回: int: 爬到n阶楼梯的不同方法数 """ # 如果只有1阶，直接返回1 if n == 1: return 1 # 初始化dp数组，dp[i]表示爬到第i阶的方法数 dp = [0] * (n + 1) dp[1] = 1 # 爬到第1阶只有1种方法 dp[2] = 2 # 爬到第2阶有2种方法：1+1或2 # 从第3阶开始计算 for i in range(3, n + 1): # 爬到第i阶的方法数 = 爬到第i-1阶的方法数 + 爬到第i-2阶的方法数 dp[i] = dp[i-1] + dp[i-2] return dp[n] # 示例测试 if __name__ == "__main__": # 示例1: n=1 n1 = 1 result1 = climbStairs(n1) print(f"示例1: n={n1}, 方法数={result1}") # 示例2: n=2 n2 = 2 result2 = climbStairs(n2) print(f"示例2: n={n2}, 方法数={result2}") # 示例3: n=3 n3 = 3 result3 = climbStairs(n3) print(f"示例3: n={n3}, 方法数={result3}") # 示例4: n=4 n4 = 4 result4 = climbStairs(n4) print(f"示例4: n={n4}, 方法数={result4}") # 示例5: n=5 n5 = 5 result5 = climbStairs(n5) print(f"示例5: n={n5}, 方法数={result5}")✅ 你会发现，这道题和斐波那契数列几乎一模一样，只是初始化不同。这就是模板的力量。
六、经典例题：零钱兑换（完全背包入门）
题目：给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
用四步走拆解
- 定义 dp 数组：
dp[i]表示凑成金额i所需的最少硬币个数 - 状态转移方程：对于每个硬币
coin，如果i >= coin，那么dp[i] = min(dp[i], dp[i - coin] + 1)意思是：凑成金额i的最少硬币数，等于凑成金额i-coin的最少硬币数加 1（加上这枚硬币） - 初始化：
dp[0] = 0（凑成金额 0 需要 0 个硬币）- 其他所有
dp[i]初始化为一个很大的数（表示无法凑成）
- 遍历顺序：从前往后遍历金额，从 1 遍历到 amount
代码
python
运行
def coinChange(coins, amount): """ 计算凑成总金额所需的最少硬币个数 参数: coins (List[int]): 不同面额的硬币 amount (int): 总金额 返回: int: 凑成总金额所需的最少硬币个数，如果无法凑成则返回-1 """ # 初始化dp数组为amount+1（一个不可能的大数） dp = [amount + 1] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for coin in coins: if i >= coin: dp[i] = min(dp[i], dp[i - coin] + 1) # 如果dp[amount]还是大于amount，说明无法凑成 return dp[amount] if dp[amount] <= amount else -1 # 示例测试 if __name__ == "__main__": # 示例1: 可以凑成的情况 coins1 = [1, 2, 5] amount1 = 11 result1 = coinChange(coins1, amount1) print(f"示例1: coins={coins1}, amount={amount1}, 最少硬币数={result1}") # 示例2: 无法凑成的情况 coins2 = [2] amount2 = 3 result2 = coinChange(coins2, amount2) print(f"示例2: coins={coins2}, amount={amount2}, 最少硬币数={result2}") # 示例3: 需要使用所有硬币的情况 coins3 = [1, 3, 4] amount3 = 6 result3 = coinChange(coins3, amount3) print(f"示例3: coins={coins3}, amount={amount3}, 最少硬币数={result3}") # 示例4: 金额为0的情况 coins4 = [1, 2, 5] amount4 = 0 result4 = coinChange(coins4, amount4) print(f"示例4: coins={coins4}, amount={amount4}, 最少硬币数={result4}") # 示例5: 大金额的情况 coins5 = [1, 2, 5] amount5 = 100 result5 = coinChange(coins5, amount5) print(f"示例5: coins={coins5}, amount={amount5}, 最少硬币数={result5}")七、常见误区
- 不要一开始就想状态转移方程：先定义好 dp 数组的含义，状态转移方程自然就出来了
- 不要死记硬背状态转移方程：要理解它的含义，知道它是怎么来的
- 动态规划不是只能用数组：很多时候可以优化空间复杂度，用几个变量代替整个数组
- 动态规划不是万能的：只有满足重叠子问题和最优子结构的问题才能用动态规划解决