什么是动态规划？

动态规划（DP）是一种通过将原问题分解为相互重叠的子问题来解决复杂问题的算法思想。它通常用于优化问题，通过存储子问题的解来避免重复计算。

核心要素

1. 最优子结构: 问题的最优解包含了其子问题的最优解。
2. 重叠子问题: 在求解过程中，许多子问题被反复计算。DP 通过存储这些解来提高效率。
3. 状态转移方程: 定义了问题状态之间如何转换的数学表达式。

经典问题：斐波那契数列