什么是动态规划？
动态规划听起来很高深，但其实就是一种”偷懒”的聪明算法。它的核心思想是：避免重复计算，把复杂问题拆解成小问题来解决。
想象你在爬楼梯，每次可以爬1步或2步。如果要爬到第10层，你可能会这样想：
- 到第10层 = 从第9层爬1步 + 从第8层爬2步
- 到第9层 = 从第8层爬1步 + 从第7层爬2步
- …
你发现了吗？计算第10层时需要知道第8层的方案数，计算第9层时也需要第8层的方案数。如果每次都重新计算第8层，就会做很多重复工作。
又如下面的例子：
- A ： “1+1+1+1+1+1+1+1 =？”
- A ： “上面等式的值是多少”
- B ： 计算 “8”
- A : 在上面等式的左边写上 “1+” 呢？
- A : “此时等式的值为多少”
- B : 很快得出答案 “9”
- A : “你怎么这么快就知道答案了”
- A : “只要在8的基础上加1就行了”
- A : “所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 ‘记住求过的解来节省时间'”
动态规划就是把这些中间结果记录下来，需要时直接查表，不用重复计算。
动态规划的三个关键要素
- 最优子结构：大问题可以分解为小问题，大问题的最优解包含小问题的最优解
- 重叠子问题：在分解过程中，会反复遇到相同的小问题
- 状态转移方程：描述问题之间关系的数学公式
经典实例：斐波那契数列
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21… 规律：F(n) = F(n-1) + F(n-2)
普通递归方法（效率低）：
pythondef fib_recursive(n):
if n <= 2:
return 1
return fib_recursive(n-1) + fib_recursive(n-2)问题：计算F(5)时，F(3)会被计算多次，造成大量重复。
动态规划方法：
pythondef fib_dp(n):
if n <= 2:
return 1
# 用数组存储已计算的结果
dp = [0] * (n + 1)
dp[1] = dp[2] = 1
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]用动态规划的思想去解题上面问题将迎刃而解，用数组dp存储已经计算过的问题的结果，后续计算时直接查表即可，避免重复计算。
动态规划的解题步骤
- 确定状态：定义dp数组的含义
- 找状态转移方程：当前状态如何由之前的状态推导出来
- 初始化：确定边界条件
- 确定遍历顺序：通常是从小到大
- 返回结果：根据题目要求返回对应的dp值
为什么动态规划这么有用？
动态规划算法就像是把一道数学题的答案写在草稿纸上，下次遇到同样的小问题就直接查表，而不用重新计算。动态规划的本质是用空间换时间，通过存储中间结果来避免重复计算，让原本指数级的时间复杂度降到多项式级别。
这就是为什么动态规划被称为”程序员的必修课”——它教会我们如何聪明地解决复杂问题。
如果你还没有弄懂，不妨来看看这个视频，也许会有收获：https://www.bilibili.com/video/BV1AB4y1w7eT/
