第四课《机器人走格子——发现状态转移》一、故事开始迷宫机器人1、在算法王国里有一台超级聪明的小机器人。它叫“格子探险家”2、有一天国王给了它一张地图□ □ □ □ □ □ □ □ □并告诉它3、“你必须从左上角走到右下角”但是机器人有个奇怪规定只能向右走 →向下走 ↓不能向左向上4、国王问“到底有多少种走法呢”5、今天我们就来帮助机器人二、题目理解1、我们把地图编号(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)2、机器人1从(1,1)出发。2目标到达(3,3)3每次只能向右向下4问一共有多少种走法三、先别急着写代码1、动态规划最重要的不是上来写代码2、而是“观察规律”3、我们先自己推一推。四、先看最简单格子1、起点(1,1)2、机器人已经在这里了。所以只有1种方法到达这里。3、于是dp[1][1] 1;五、再看第一行1、比如(1,2)怎么到2、只能从左边(1,1)走过来3、所以dp[1][2] 1;4、同理(1,3)也只有1种方法。5、因为第一行不能从上面来六、再看第一列1、比如(2,1)2、只能从上面(1,1)下来。3、所以dp[2][1] 1;4、同理第一列所有格子也都只有1种方法。七、真正关键来了1、现在看中间格子(2,2)机器人怎么到这里2、最后一步只有两种可能1情况1从上面(1,2)下来。2情况2从左边(2,1)走来。3所以到(2,2)的方法数 到(1,2)的方法数 到(2,1)的方法数3、于是dp[2][2]dp[1][2]dp[2][1]八、发现规律1、对于任意格子(i,j)2、都只能从上面来从左边来3、所以状态转移公式dp[i][j]dp[i-1][j]dp[i][j-1]九、这就是二维DP1、前几课我们学的是dp[i]2、今天升级了变成dp[i][j]3、因为地图有行列4、所以需要二维数组十、手动画表格1、现在我们一步一步填表。2、初始123111121??31??3、计算 dp[2][2]1 1 24、表格变成1231111212?31??5、计算 dp[2][3]来自上面 dp[1][3]左边 dp[2][2]1 2 3表格1231111212331??6、计算 dp[3][2]2 1 37、计算 dp[3][3]3 3 6最终1231111212331368、答案6十一、参考代码#include iostream using namespace std; int dp[105][105]; int main() { int n 3; int m 3; // 第一行 for(int j 1; j m; j) { dp[1][j] 1; } // 第一列 for(int i 1; i n; i) { dp[i][1] 1; } // 状态转移 for(int i 2; i n; i) { for(int j 2; j m; j) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } cout dp[n][m]; return 0; }十二、程序运行过程程序会第一步初始化第一行、第一列。第二步从左到右从上到下慢慢填表。第三步最后dp[n][m]就是答案十三、动态规划真正的感觉很多同学现在会发现1、目前学的DP很像“填地图”2、因为每个格子的答案都来自周围格子。3、这就是状态转移十四、动态规划四步法再次强化以后同学们使用所有DP都尽量按这四步第一步定义状态这里dp[i][j]表示“走到(i,j)的方法数”第二步初始化第一行全是1。第一列全是1。第三步找转移dp[i][j]dp[i-1][j]dp[i][j-1]第四步确定顺序从左上角慢慢往右下角推。十五、课堂挑战挑战1如果地图是4 × 4答案是多少请自己画表挑战2修改程序输入n 和 m输出机器人走法数。挑战3如果地图里有障碍物X机器人不能经过。该怎么办提示障碍物位置dp[i][j] 0;十六、举一反三今天我们学的这道题是不是很简单但是很多DP都是从它变来的比如游戏地图迷宫问题最短路径最少花费路径统计十七、本课总结✅1、二维DP使用dp[i][j]✅2、状态表示到某个格子的方法数。✅3、状态转移来自上面左边✅4、动态规划本质利用小答案推大答案✅5、DP最核心状态 转移十八、第一阶段总结恭喜同学们我们已经完成⚔️动态规划启蒙篇⚔️现在同学们已经学会递归记忆化搜索DP数组状态转移二维DP通车们已经正式进入动态规划的大门下阶段预告接下来我们进入⚔️第二阶段线性DP⚔️第一课《青蛙跳台阶大赛》这次青蛙不止能跳2步了看看状态转移还能怎么玩