第三课《表格王国——动态规划真正登场》一、故事开始魔法书升级了1、上一节课递归精灵得到了一本记忆魔法书2、它终于学会了“算过的别再算”3、于是程序速度变快了很多4、但是算法王国的大法师却摇了摇头“你虽然会记忆化搜索了……”“可你还是太依赖递归了”5、递归精灵一愣“还有更厉害的方法”6、大法师点点头“真正的动态规划DP是可以自己一步一步推答案”7、今天我们就进入⚔️真正的动态规划DP⚔️二、今天的任务1、还是经典问题爬楼梯2、题目有 n 层楼梯。每次可以走1层可以走2层问一共有多少种走法三、以前的方法1、以前我们用递归2、像这样f(n) f(n-1) f(n-2)3、然后不断往下递归。4、虽然有 memo 数组帮助。但本质还是“先问大问题”再拆小问题。5、这叫自顶向下四、今天的新方法1、今天我们不用递归了2、而是从小到大一步一步自己推答案3、就像搭积木4、先搭第一层第二层再慢慢搭高。五、动态规划数组登场1、今天主角来了✨dp数组✨2、我们定义dp[i]表示3、“走到第i层的方法数”比如dp[3]表示走到第3层的方法数dp[5]表示走到第5层的方法数六、先填最简单的答案1、动态规划里最重要的一步先写初始状态2、第1层只有1一种。所以dp[1] 1;3、第2层有11 2两种。所以dp[2] 2;七、开始推后面的答案1、现在我们思考dp[3]怎么来2、最后一步只有两种情况1情况1从第2层走1步。2情况2从第1层走2步。3所以dp[3]dp[2]dp[1]3、同理dp[4]来自dp[3]dp[2]所以dp[4]dp[3]dp[2]4、发现规律了吗5、通用公式dp[i]dp[i-1]dp[i-2]八、这就是“状态转移”1、当前状态dp[i]由前面的状态dp[i-1] dp[i-2]推出来。2、这就叫状态转移九、画表格理解1、假设n 62、我们一步一步填表idp[i]11223345586133、怎么得到的1dp[3]1 2 32dp[4]3 2 53dp[5]5 3 84、大家发现动态规划像填表十、参考代码#include iostream using namespace std; int dp[100]; int main() { int n; cin n; // 初始状态 dp[1] 1; dp[2] 2; // 状态转移 for(int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } cout dp[n]; return 0; }十一、程序运行模拟假设n 5开始第一步dp[1] 1 dp[2] 2第二步dp[3] dp[2] dp[1] 2 1 3第三步dp[4] dp[3] dp[2] 3 2 5第四步dp[5] dp[4] dp[3] 5 3 8输出8十二、DP和记忆化搜索的区别很多同学会疑惑1、“这和上一课有什么区别”2、上一课是递归 记忆属于自顶向下3、今天是直接填表属于自底向上4、区别1记忆化搜索先问大问题 再递归拆小问题2动态规划从最小问题开始 一步一步推到大问题十三、为什么DP这么强1、因为它通常更快2、而且不用递归3、所以不容易爆栈更稳定更适合竞赛十四、动态规划四大步骤以后做DP题一定按这四步第一步定义状态比如dp[i]表示什么这里走到第i层的方法数第二步写初始状态dp[1] 1 dp[2] 2第三步找状态转移dp[i]dp[i-1]dp[i-2]第四步计算顺序从小到大。十五、课堂挑战挑战1如果每次可以走1层可以走2层可以走3层状态转移方程是什么提示最后一步可能来自i-1i-2i-3挑战2自己手推n 7的dp表。挑战3修改程序输出整个dp数组。例如1 2 3 5 8 13十六、举一反三1、以后看到“大问题依赖小问题”2、同学们可以想能不能DP3、比如青蛙跳台阶铺地板硬币问题游戏最优路线背包问题十七、本课总结✅1、dp数组表示状态✅2、动态规划是“填表法”✅3、状态转移是DP核心✅4、DP通常从小到大推答案✅5、DP四大步骤定义状态初始化状态转移计算顺序十八、下节课预告下一节课⚔️《机器人走格子——发现状态转移》⚔️我们将进入二维动态规划机器人只能向右向下看看它到底有多少种走法