第二课
《记忆魔法书——记忆化搜索》
🌟一、上节课回顾
1、上一节课里，
我们认识了：
✨递归精灵✨
它特别聪明。
但是！
有一个超级大的问题：
😵它太健忘了！
明明已经算过：
f(3)结果过一会儿：
又重新算一次！
于是：
程序越来越慢……
2、今天，
我们要送给递归精灵一本：
📖《记忆魔法书》
让它：
🌟算过一次，就永远记住！
🌟二、今天要解决的问题
1、还是老问题：
🪜爬楼梯问题
2、📖题目
有 n 层楼梯。
每次：
可以走1层
可以走2层
问：
一共有多少种走法？
🌟三、暴力递归的问题
1、先看看旧代码：
int f(int n) { if(n == 1) return 1; if(n == 2) return 2; return f(n - 1) + f(n - 2); }2、比如：
f(5)会变成：
f(4) + f(3)而：
f(4)里面又有：
f(3)3、结果：
f(3)被重复计算！
🌟四、怎么办？
1、递归精灵突然想到：
✨“我为什么不把答案记下来呢？”✨
2、比如：
第一次算出：
f(3)=3就写进魔法书。
下次再需要：
f(3)时，
直接翻书！
不用重新算！
3、这就是:
记忆化搜索
🌟五、✨记忆化搜索✨
其实意思特别简单：
1、🌟记忆化
就是：
“记住答案”
2、🌟搜索
就是：
“递归继续搜索”
3、合起来：
🌟一边递归，一边记答案！
🌟六、准备一本“记忆魔法书”
1、我们需要一个数组：
int memo[100];2、它的作用：
（1）memo[3]
表示：
f(3)的答案。
（2）比如：
memo[3] = 3说明：
f(3)已经算过啦！
🌟七、记忆化搜索流程
现在流程变成：
第一步
先看看：
memo[n]有没有答案。
第二步
如果有：
直接返回！
第三步
如果没有：
再递归计算。
第四步
算完以后：
存进 memo。
🌟八、参考代码
#include <iostream> using namespace std; int memo[100]; // 计算走到第n层的方法数 int f(int n) { // 边界 if(n == 1) return 1; if(n == 2) return 2; // 如果已经算过 if(memo[n] != 0) { return memo[n]; } // 没算过，递归计算 memo[n] = f(n - 1) + f(n - 2); return memo[n]; } int main() { int n; cin >> n; cout << f(n); return 0; }🌟九、程序运行过程
1、假设：
n = 52、程序开始：
计算：
f(5)3、发现：
memo[5]=0说明：
没算过！
4、于是：
开始计算：
f(4)+f(3)5、计算完：
f(3)=3后，
程序会：
memo[3] = 3;6、以后再遇到：
f(3)时，
直接：
return memo[3];🌟十、这次快了多少？
1、以前：
f(40)可能会算：
几亿次！
2、现在：
每个数字：
只算一次！
也就是说：
f(1)
算一次
f(2)
算一次
f(3)
算一次
……
f(40)
也只算一次！
3、🌟这就是：
🚀空间换时间！
4、我们用了：
一个数组空间。
换来了：
程序速度暴增！
🌟十一、形象理解
1、以前：
f(3)会重复出现很多次。
2、现在：
第一次：
f(3)真正计算。
3、后面：
全部：
📖查魔法书！
就像：
4、🍎考试时
你已经会：
7×8=56以后再也不用：
重新掰手指头！
🌟十二、什么叫“状态”？
1、在动态规划里，
有一个特别重要的词：
🌟状态
2、这里：
f(n)就是一个状态。
3、因为：
它表示：
“走到第n层的方法数”
4、以后：
我们会遇到：
dp[i] dp[i][j]这些都是表达的：
状态
🌟十三、什么叫“转移”？
1、这里：
f(n)=f(n-1)+f(n-2)
就是：
🌟状态转移
2、意思是：
当前答案
从：
前面的答案
推过来。
🌟十四、本课总结
1、今天讲解的内容：
🌟记忆化搜索 = 🌟递归 与 🌟记忆数组
这本身就是一种：
“自顶向下”的动态规划！
2、什么意思？
从：
f(n)开始，
不断往下递归。
需要谁，
就计算谁。
🌟十五、课堂挑战
🎯挑战1
课堂例题的爬楼梯问题：
输入：
7程序输出多少？
请自己手算试试。
🎯挑战2
（1）如果：
每次：
可以走1层
可以走2层
可以走3层
程序应该怎么修改？
（2）提示：
最后一步：
可能来自：
n-1
n-2
n-3
🌟十六、举一反三
记忆化搜索不仅能解决楼梯问题。
还能解决：
🐸青蛙跳台阶
🪙凑硬币
🎮游戏最短路线
🧱铺砖块
🌳树形搜索
只要：
“问题会重复出现”
就可以考虑：
✨记忆化搜索✨
🌟十七、本课总结
✅1、递归会重复计算
✅2、memo数组可以保存答案
✅3、算过的直接返回
✅4、这叫：
🌟记忆化搜索
🌟十八、下节课预告
下一节课：
⚔️《表格王国——动态规划真正登场》⚔️
我们将学习：
🌟不用递归！
直接用表格推答案！
真正的：
DP数组
要正式登场啦！
