第三阶段第三课⚔️《机器人迷宫寻宝——网格路径DP》一、故事开始机器人寻宝大赛1、在算法王国里住着一个聪明的小机器人阿铁2、有一天国王宣布机器人寻宝大赛开始啦3、比赛场地是一座巨大的宝藏迷宫。迷宫长这样□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □4、每个格子里都可能藏着金币。5、阿铁从左上角出发 □ □ □ □ □ □ □ □ □ □ □ □ □ □ 6、目标是走到右下角宝藏屋7、但是有规则只能向右走或者只能向下走8、例如可以这样→ → ↓ ↓ →但不能← ↑因为机器人不会倒着走二、第一个问题1、国王问一共有多少种走法2、例如2×2地图S □ □ E从S到E。3、机器人必须右 下或者下 右4、所以答案2三、暴力法会怎样1、如果地图越来越大10 × 102、机器人每次都要选择向右 还是向下3、路线会越来越多如果100 × 1004、暴力搜索几乎不可能完成。于是⚔️DP再次登场四、观察地图1、我们画一个3×3地图(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)2、目标从(1,1)走到(3,3)五、定义状态1、定义dp[i][j]表示到达(i,j)位置的方法数2、例如dp[2][3]表示到达第2行第3列的方法数。六、最关键的问题1、来到(2,2)2、机器人怎么来的看看地图□ □ □ □ X □ □ □ □机器人只能从上面来(1,2) ↓ (2,2)或者从左边来(2,1) → (2,2)不会有第三种情况。3、所以到达当前格的方法数 上面的方法数 左边的方法数状态转移来了dp[i][j]dp[i-1][j]dp[i][j-1]七、为什么是加法1、因为从上面来的路线和从左边来的路线完全不同2、例如到达这里□ □ □ □ □ X上面有1条路。左边有2条路。那么总共1 2 3条路。所以要相加八、初始化1、看看第一行□ □ □ □机器人只能一直向右。2、所以dp[1][1]1 dp[1][2]1 dp[1][3]1 dp[1][4]1第一列同理dp[1][1]1 dp[2][1]1 dp[3][1]1 dp[4][1]1九、开始填表1、3×3地图1第一行1 1 12第一列1 1 13现在算(2,2)4上面15左边16得到27继续(2,3)8上面19左边210得到311继续填1 1 1 1 2 3 1 3 612最后dp[3][3]62、答案6种走法十、可以把DP表理解成流水1、想象每个格子是一座小水池。2、水从起点流出来3、每到一个格子都会把水流向右边 下边4、于是每个格子里的水量就是左边流来的 上面流来的5、这就是dp[i][j]的来源十一、升级版地图里有障碍物1、有一天迷宫里出现了石头2、例如S □ □ □ ■ □ □ □ E中间■不能走怎么办3、非常简单如果block[i][j] true说明是石头。那么dp[i][j]0;因为根本到不了十二、参考代码无障碍版#include iostream using namespace std; int dp[105][105]; int main() { int n,m; cin n m; dp[1][1] 1; for(int i1;in;i) { for(int j1;jm;j) { if(i1 j1) continue; dp[i][j] dp[i-1][j] dp[i][j-1]; } } cout dp[n][m]; return 0; }十三、参考代码障碍物版本#include iostream using namespace std; int dp[105][105]; bool block[105][105]; int main() { int n,m,k; cin n m; cin k; for(int i1;ik;i) { int x,y; cin x y; block[x][y]true; } dp[1][1]1; for(int i1;in;i) { for(int j1;jm;j) { if(i1 j1) continue; if(block[i][j]) { dp[i][j]0; continue; } dp[i][j] dp[i-1][j] dp[i][j-1]; } } coutdp[n][m]; return 0; }十四、手工模拟障碍物1、地图S □ □ □ ■ □ □ □ E2、DP表1 1 1 1 0 1 1 1 23、答案2只有两条合法路线。十五、哪些类型题目是网格DP下列很多都是它变来的例如游戏地图汽车导航机器人规划迷宫寻路火箭发射路径本质都是网格DP十六、课堂挑战挑战1计算4 × 4地图到终点共有多少种走法挑战2地图S □ □ □ ■ □ □ □ E请手工填写DP表。挑战3如果机器人可以右 下 右下斜走三种方向状态转移如何修改提示多一个来源。挑战4如果每个格子有金币1 3 2 5 4 1 2 8 6机器人经过格子就能拿金币。如何求最大金币数这就是下一类DP网格最优路径DP十七、本课总结✅状态定义dp[i][j]表示到达(i,j)的方法数✅状态转移dp[i][j]dp[i-1][j]dp[i][j-1]✅初始化第一行全是1第一列全是1✅障碍物dp[i][j]0;✅这是经典的二维DP模型之一下节课预告下一课⚔️《黄金矿工大赛——网格最大价值DP》⚔️我们将学习不是求有多少条路而是求哪条路最值钱这将是二维DP中的另一位超级明星。
GESP6级C++考试语法知识（四十六、动态规划----二维DP（三、网格路径DP）
第三阶段第三课⚔️《机器人迷宫寻宝——网格路径DP》一、故事开始机器人寻宝大赛1、在算法王国里住着一个聪明的小机器人阿铁2、有一天国王宣布机器人寻宝大赛开始啦3、比赛场地是一座巨大的宝藏迷宫。迷宫长这样□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □4、每个格子里都可能藏着金币。5、阿铁从左上角出发 □ □ □ □ □ □ □ □ □ □ □ □ □ □ 6、目标是走到右下角宝藏屋7、但是有规则只能向右走或者只能向下走8、例如可以这样→ → ↓ ↓ →但不能← ↑因为机器人不会倒着走二、第一个问题1、国王问一共有多少种走法2、例如2×2地图S □ □ E从S到E。3、机器人必须右 下或者下 右4、所以答案2三、暴力法会怎样1、如果地图越来越大10 × 102、机器人每次都要选择向右 还是向下3、路线会越来越多如果100 × 1004、暴力搜索几乎不可能完成。于是⚔️DP再次登场四、观察地图1、我们画一个3×3地图(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)2、目标从(1,1)走到(3,3)五、定义状态1、定义dp[i][j]表示到达(i,j)位置的方法数2、例如dp[2][3]表示到达第2行第3列的方法数。六、最关键的问题1、来到(2,2)2、机器人怎么来的看看地图□ □ □ □ X □ □ □ □机器人只能从上面来(1,2) ↓ (2,2)或者从左边来(2,1) → (2,2)不会有第三种情况。3、所以到达当前格的方法数 上面的方法数 左边的方法数状态转移来了dp[i][j]dp[i-1][j]dp[i][j-1]七、为什么是加法1、因为从上面来的路线和从左边来的路线完全不同2、例如到达这里□ □ □ □ □ X上面有1条路。左边有2条路。那么总共1 2 3条路。所以要相加八、初始化1、看看第一行□ □ □ □机器人只能一直向右。2、所以dp[1][1]1 dp[1][2]1 dp[1][3]1 dp[1][4]1第一列同理dp[1][1]1 dp[2][1]1 dp[3][1]1 dp[4][1]1九、开始填表1、3×3地图1第一行1 1 12第一列1 1 13现在算(2,2)4上面15左边16得到27继续(2,3)8上面19左边210得到311继续填1 1 1 1 2 3 1 3 612最后dp[3][3]62、答案6种走法十、可以把DP表理解成流水1、想象每个格子是一座小水池。2、水从起点流出来3、每到一个格子都会把水流向右边 下边4、于是每个格子里的水量就是左边流来的 上面流来的5、这就是dp[i][j]的来源十一、升级版地图里有障碍物1、有一天迷宫里出现了石头2、例如S □ □ □ ■ □ □ □ E中间■不能走怎么办3、非常简单如果block[i][j] true说明是石头。那么dp[i][j]0;因为根本到不了十二、参考代码无障碍版#include iostream using namespace std; int dp[105][105]; int main() { int n,m; cin n m; dp[1][1] 1; for(int i1;in;i) { for(int j1;jm;j) { if(i1 j1) continue; dp[i][j] dp[i-1][j] dp[i][j-1]; } } cout dp[n][m]; return 0; }十三、参考代码障碍物版本#include iostream using namespace std; int dp[105][105]; bool block[105][105]; int main() { int n,m,k; cin n m; cin k; for(int i1;ik;i) { int x,y; cin x y; block[x][y]true; } dp[1][1]1; for(int i1;in;i) { for(int j1;jm;j) { if(i1 j1) continue; if(block[i][j]) { dp[i][j]0; continue; } dp[i][j] dp[i-1][j] dp[i][j-1]; } } coutdp[n][m]; return 0; }十四、手工模拟障碍物1、地图S □ □ □ ■ □ □ □ E2、DP表1 1 1 1 0 1 1 1 23、答案2只有两条合法路线。十五、哪些类型题目是网格DP下列很多都是它变来的例如游戏地图汽车导航机器人规划迷宫寻路火箭发射路径本质都是网格DP十六、课堂挑战挑战1计算4 × 4地图到终点共有多少种走法挑战2地图S □ □ □ ■ □ □ □ E请手工填写DP表。挑战3如果机器人可以右 下 右下斜走三种方向状态转移如何修改提示多一个来源。挑战4如果每个格子有金币1 3 2 5 4 1 2 8 6机器人经过格子就能拿金币。如何求最大金币数这就是下一类DP网格最优路径DP十七、本课总结✅状态定义dp[i][j]表示到达(i,j)的方法数✅状态转移dp[i][j]dp[i-1][j]dp[i][j-1]✅初始化第一行全是1第一列全是1✅障碍物dp[i][j]0;✅这是经典的二维DP模型之一下节课预告下一课⚔️《黄金矿工大赛——网格最大价值DP》⚔️我们将学习不是求有多少条路而是求哪条路最值钱这将是二维DP中的另一位超级明星。
