第一课《健忘的小精灵——什么是重复计算》一、故事开始健忘的小精灵1、在很远很远的算法王国里住着一只小精灵。它的名字叫✨“递归精灵”✨递归精灵特别聪明。别人不会的问题它都会。有一天国王问它2、“如果有5层楼梯每次可以走1层或者2层一共有多少种走法呢”递归精灵立刻开始思考到第5层可以从第4层走1步上来或者从第3层走2步上来所以到第5层的方法数 到第4层的方法数 到第3层的方法数3、于是他继续计算第4层又需要第3层第2层第3层又需要第2层第1层结果……越算越乱因为发现自己一直在重复计算比如第3层算了好多次第2层更是算了无数次小精灵累得直接趴下了……二、今天我们要学什么1、今天这节课我们不急着学动态规划。我们先了解什么叫“重复计算”2、动态规划的真正起点不是DP数组而是✨发现重复劳动✨三、楼梯问题现在我们正式开始。1、题目有 n 层楼梯。每次可以走1层或者走2层问一共有多少种走法四、先从小情况开始1、1层楼只有1一种。所以f(1)12、2层楼可以11 2两种。所以f(2)23、3层楼可以111 12 21三种。所以f(3)34、4层楼我们来认真分析最后一步只有两种情况情况1最后走1层。那前面必须先到第3层情况2最后走2层。那前面必须先到第2层所以到第4层的方法数 到第3层的方法数 到第2层的方法数也就是f(4)f(3)f(2)代入3 2 5五、神奇规律出现了1、我们继续观察f(1)1f(2)2f(3)3f(4)52、发现后面的答案都是前两个答案相加所以公式来了f(n)f(n-1)f(n-2) ;斐波那契数列六、用递归解决这个问题于是递归精灵写出了代码#include iostream using namespace std; int f(int n) { // 边界 if(n 1) return 1; if(n 2) return 2; // 递归 return f(n - 1) f(n - 2); } int main() { int n; cin n; cout f(n); return 0; }七、程序是怎么运行的1、假设n 5那么2、f(5)需要f(4) f(3)3、而f(4)又需要f(3) f(2)4、注意这里f(3)是不是已经算过一次了结果又算了一次5、继续展开f(5) ├── f(4) │ ├── f(3) │ │ ├── f(2) │ │ └── f(1) │ └── f(2) └── f(3) ├── f(2) └── f(1)6、大家发现了吗f(3)被计算了两次f(2)更惨被计算了三次八、这就叫重复计算1、程序明明已经知道f(3)3结果它转头就忘了又重新算这就像2、小朋友做数学题刚算完325下一秒又重新掰手指头……太浪费时间啦九、数据变大会怎样如果n 40那么程序会疯狂重复计算电脑会变得超级慢十、为什么会重复因为递归树里很多“小问题”会反复出现。比如f(20)可能被算几千次十一、动态规划真正的思想今天最重要的一句话来了动态规划的核心“已经算过的东西不要再算”这就是DP思想的起点十二、课堂小游戏现在请同学们思考问题1计算f(6)时哪些数字会重复计算问题2如果f(100)会不会特别慢为什么问题3有没有办法让程序记住以前算过的答案十三、举一反三其实很多问题都会重复计算。比如青蛙跳台阶铺地板游戏通关凑硬币只要“小问题反复出现”就可能使用✨动态规划✨十四、本课总结今天学会了什么✅1、递归会拆分小问题✅2、小问题可能重复出现✅3、重复计算会让程序变慢✅4、动态规划的核心思想“算过的不再重复算”下节课预告下一节课⚔️《记忆魔法书——记忆化搜索》⚔️我们要教递归精灵✨如何“记住答案”这样它就不会反复重复计算啦