动态规划是一种通过将大问题拆解为小问题并存储中间结果来优化计算的算法思想。它结合了分治法和记忆法，通过记录子问题的解避免重复计算，适用于具有重叠子问题和最优子结构的问题。典型例子包括爬楼梯、公交换乘和背包问题，其核心是分阶段解决、存储中间结果并逐步推导最终答案。形象地说，动态规划就像在爬楼梯时每层贴备忘纸条，直接查结果而不重复计算，从而高效解决问题。
一、动态规划是什么？（形象比喻）
1. '爬楼梯'的故事
想象你要爬一栋 10 层的楼，每次可以选择爬 1 层或者 2 层。你想知道：有多少种不同的爬法？
如果你每次都从头开始算，10 层、9 层、8 层……会发现很多重复计算，非常麻烦。
动态规划的思想就像是：
- 你在每一层楼梯口都贴一张纸，写上'从这里到顶楼有多少种爬法'。
- 当你需要知道从第 5 层怎么爬到顶楼时，先看看第 6 层和第 7 层的纸条（因为你下一步只能爬 1 层或 2 层），把它们的数字加起来，就是第 5 层的答案。
- 这样，每一层只算一次，后面需要时直接查纸条，省时省力！
2. '记忆法'与'分治法'的结合
- 分治法：把大问题拆成小问题，逐步解决。
- 记忆法：把已经算过的小问题结果记下来，避免重复劳动。
动态规划就是把这两种方法结合起来，既拆分问题，又记住结果。
二、生活中的动态规划例子
1. 最省钱的公交换乘
你要从家到公司，中间有很多公交线路和换乘点。每一段路有不同的票价。你想知道：怎样换乘，花的钱最少？
- 动态规划会让你从终点往回推，每到一个换乘点，记下'从这里到终点的最省钱方案'。
- 这样，每个换乘点只算一次，最后就能找到全程最省钱的路线。
2. 背包问题
你有一个背包和一堆物品，每个物品有重量和价值，背包容量有限。怎样装，才能让背包里的总价值最大？
- 动态规划会把'装前 n 个物品、容量为 k 的背包最大价值'这个问题拆成更小的子问题，并把每个子问题的答案记下来，避免重复计算。
三、动态规划的核心思想
- 把大问题拆成小问题（分阶段、分步骤解决）
- 每个小问题只算一次（用表格或数组把结果记下来）
- 从小到大逐步推导出最终答案
四、形象总结
- 动态规划就像爬楼梯时在每一层贴备忘纸条，每次只要查纸条就能知道答案，避免重复爬。
- 它适合有重叠子问题和最优子结构的问题（即大问题的最优解可以由小问题的最优解推出来）。
动态规划就是'把大问题拆小，算过的记下来，下次直接查'，让复杂问题变得高效、简单！