企业官网建设流程全解析

第三阶段第三课⚔️

🤖《机器人迷宫寻宝——网格路径DP》

🌟一、故事开始：机器人寻宝大赛

1、在算法王国里，

住着一个聪明的小机器人：

🤖阿铁

2、有一天，

国王宣布：

🏆机器人寻宝大赛开始啦！

3、比赛场地是一座巨大的宝藏迷宫。

迷宫长这样：

□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □

4、每个格子里，

都可能藏着金币。

5、阿铁从左上角出发：

🤖 □ □ □ □ □ □ □ □ □ □ □ □ □ □ 🏆

6、目标是：

🌟走到右下角宝藏屋！

7、但是有规则：

只能向右走

或者

只能向下走

8、例如：

可以这样：

→ → ↓ ↓ →

但不能：

← ↑

因为机器人不会倒着走！

🌟二、第一个问题

1、国王问：

🌟一共有多少种走法？

2、例如：

2×2地图：

S □ □ E

从S到E。

3、机器人必须：

右 下

或者：

下 右

4、所以：

答案：

2

🌟三、暴力法会怎样？

1、如果地图越来越大：

10 × 10

2、机器人每次都要选择：

向右？ 还是向下？

3、路线会越来越多！

如果：

100 × 100

4、暴力搜索几乎不可能完成。

于是：

⚔️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 1

（2）第一列：

1 1 1

（3）现在算：

(2,2)

（4）上面：

1

（5）左边：

1

（6）得到：

2

（7）继续：

(2,3)

（8）上面：

1

（9）左边：

2

（10）得到：

3

（11）继续填：

1 1 1 1 2 3 1 3 6

（12）最后：

dp[3][3]=6

2、答案：

🌟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 i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(i==1 && j==1) 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 i=1;i<=k;i++) { int x,y; cin >> x >> y; block[x][y]=true; } dp[1][1]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(i==1 && j==1) continue; if(block[i][j]) { dp[i][j]=0; continue; } dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } cout<<dp[n][m]; return 0; }

🌟十四、手工模拟障碍物

1、地图：

S □ □ □ ■ □ □ □ E

2、DP表：

1 1 1 1 0 1 1 1 2

3、答案：

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中的另一位超级明星。