🧠
递归与回溯
动态规划入门
📖知识引入
🧩最优子结构
大问题的最优解由子问题的最优解组成
🔄重叠子问题
子问题会被重复计算，用备忘录避免
📝备忘录
记录已计算的结果，避免重复计算
📊状态转移
从已知状态推导新状态，如dp[i]=dp[i-1]+dp[i-2]
⚡自底向上
从最小问题开始填表，逐步推导到大问题
🔍简单DP入门示例
📝简单DP入门示例
💻
点击「运行」查看输出
DP vs 纯递归（以斐波那契为例）：
纯递归：fib(5)会重复计算fib(3)两次
fib(5)
/ \
fib(4) fib(3) ← 重复！
/ \
fib(3) fib(2) ← 又重复！DP用备忘录：算过的存起来 dp[0]=0 dp[1]=1 dp[2]=dp[1]+dp[0]=1 dp[3]=dp[2]+dp[1]=2 dp[4]=dp[3]+dp[2]=3 dp[5]=dp[4]+dp[3]=5
每个值只算一次，快很多！
🎯小测验
第1题：DP的核心思想是？
第2题：DP和递归的区别？
第3题：DP中dp[n]!=0表示什么？
📝本课知识点
- ✓最优子结构
- ✓重叠子问题
- ✓备忘录避免重复计算
- ✓状态转移方程
- ✓DP比纯递归快很多
第35课完成！继续探索下一课吧 🚀