什么是动态规划？

动态规划是一种将复杂问题分解为更小的子问题，并存储子问题的解以避免重复计算的高效算法思想。简单说就是：“记住你已经算过的东西，别再重复计算了”

核心思想：三大特征

1. 重叠子问题：问题可以分解为相似的子问题
2. 最优子结构：问题的最优解包含子问题的最优解
3. 状态转移：可以通过子问题的解推导出原问题的解

1. 这个问题能分解成小问题吗？
   ↓
2. 小问题的结果会被重复使用吗？
   ↓
3. 我该记录什么状态？(定义dp)
   ↓
4. 如何用小问题的解得到大问题的解？(状态转移)
   ↓
5. 最简单的情况是什么？(初始化)
   ↓
6. 最后要什么结果？(计算答案)

识别动态规划问题 🔍

看到这些关键词就要想到动态规划：

• 求"最大值/最小值"
• 求"有多少种方法"
• "能不能"做到某件事
• 有"选择"的问题（拿/不拿，走/不走）

四步法解决动态规划问题 🏅

当你遇到一个问题时，可以这样思考：

1. 定义状态：dp[i] 或 dp[i][j] 表示什么？
2. 状态转移方程：如何从已知状态推导出新状态？
3. 初始条件：最基础的情况是什么？
4. 计算结果：最终要返回什么？