登录以参加训练计划

什么是动态规划？

想象你要组装一个超大的乐高城堡！如果直接从最顶层开始拼，可能会手忙脚乱。但如果一层一层从下往上搭，每一步都稳稳的，最后就能轻松完成啦！

动态规划就像这样：把大问题拆成小问题，先解决小问题，再用小问题的答案一步步解决大问题！

---

🐾 一维动态规划是什么？

用一个魔法数组（比如叫 dp）来记录每一步的答案！

就像小兔子跳台阶的题目：

题目：

小兔子要跳上第 5 级台阶，每次能跳 1 级或 2 级。有多少种不同的跳法？

用动态规划解决：

分解问题： 跳到第 5 级台阶的跳法 =
（跳到第 4 级的跳法 + 再跳 1 级）
+
（跳到第 3 级的跳法 + 再跳 2 级）

魔法数组 dp：

• dp[0] = 1（站在地面算 1 种方法）
• dp[1] = 1（跳到第 1 级只有 1 种方法）
• dp[2] = dp[1] + dp[0] = 2
• dp[3] = dp[2] + dp[1] = 3
• ……
• 一直算到 dp[5] = 8！

规律公式： dp[n] = dp[n-1] + dp[n-2]（因为最后一步可能是跳 1 级或 2 级）

---

✨ 一维动态规划的秘诀

• 拆解问题： 把大问题变成更小的同类问题（比如跳 5 级→跳 4 级 + 跳 3 级）。

• 记住答案： 用数组 dp 记录每个小问题的答案，避免重复计算。

• 逐步解决： 像搭积木一样，从最底层开始，一步步算到目标！

---

🌰 举个栗子：存钱罐问题

你有 1元、2元硬币，存满 4元有多少种组合？

动态规划解法：

• 魔法数组 dp： dp[i] 表示存满 i 元的方法数。
• 初始值：
  • dp[0] = 1（0元只有“不放硬币”1种方法）
• 递推公式：
  • 如果加上 1元硬币：dp[i] += dp[i-1]
  • 如果加上 2元硬币：dp[i] += dp[i-2]
• 结果：
  • dp[4] = 5（1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2）

---

🌈 总结

一维动态规划就像魔法笔记本：

• 把大问题拆成小问题，
• 把每个小问题的答案记在本子上，
• 用已有的答案一步步算出大问题的解！

下次遇到难题时，试试这个方法吧！😊