GESP6级C++考试语法知识（四十五、动态规划----二维DP（二、数字三角形）

第三阶段第二课

💎《宝石矿洞探险——数字三角形》

🌟一、故事开始：神秘的宝石矿洞

1、在算法王国的地下，

有一个传说中的地方：

💎宝石矿洞💎

矿洞里堆满了宝石！

每个房间都有不同数量的宝石。

2、有一天，

小勇士阿呆接到任务：

3、🌟从矿洞顶部出发

🌟一路走到底部

🌟要收集尽可能多的宝石

4、国王说：

收集到的宝石越多，

奖励就越丰厚！

5、阿呆高兴极了：

我要成为宝石大王！

6、可是矿洞很特殊。

它长这样：

5 8 4 3 6 9 7 2 1 8

这就是著名的：

🌟数字三角形

🌟二、矿洞移动规则

1、阿呆从顶部开始：

5

2、每次只能往下一层走。

而且：

如果站在这里：

8

下一步只能去：

3 或 6

不能直接跳到：

9

因为：

🚫太远了！

3、所以规则是：

每次只能走到下一层相邻的位置

例如：

5 8 4

从5出发，

只能去：

8

或者：

4

🌟三、先用暴力思考

1、假设：

5 8 4 3 6 9

（1）路线1：

5 → 8 → 3

宝石：

16

（2）路线2：

5 → 8 → 6

宝石：

19

（3）路线3：

5 → 4 → 6

宝石：

15

（4）路线4：

5 → 4 → 9

宝石：

18

（5）答案：

19

2、可是如果有100层呢？

路线数量会爆炸！

3、所以：

⚔️动态规划登场！

🌟四、先观察规律

1、看这个三角形：

5 8 4 3 6 9 7 2 1 8

2、假设：

阿呆已经来到：

6

他想知道：

从这里出发

到最底层

最多还能获得多少宝石？

这是不是和原问题很像？

3、我们发现：

🌟大问题里面藏着小问题！

这正是DP最喜欢的情况！

🌟五、定义状态

1、我们定义：

dp[i][j]

表示：

2、从位置(i,j)出发

一直到最底层

能获得的最大宝石数

（1）例如：

5 8 4 3 6 9 7 2 1 8

（2）数字6的位置：

dp[3][2]

表示：

（3）从6开始，

走到底部，

最多能得到多少宝石。

🌟六、最重要的一步

1、来到：

6

（1）下面有两个选择：

2

或者：

1

（2）阿呆会怎么选？

当然选宝石更多的路！

所以：

当前位置价值 + 下面两条路中的最大值

2、状态转移公式来了：

dp[i][j] = a[i][j] + max(dp[i+1][j],dp[i+1][j+1])

这句话非常重要！

意思是：

当前位置宝石

+

左下路线最大收益

和

右下路线最大收益

中的较大者

🌟七、为什么我们要从下面开始算？

1、我们来看看最底层：

7 2 1 8

2、如果已经到底了，

还能往哪走？

哪也不用走！

3、所以：

dp[4][1]=7 dp[4][2]=2 dp[4][3]=1 dp[4][4]=8

4、这就是DP的：

🌟初始化

🌟八、开始填表

1、原三角形：

5 8 4 3 6 9 7 2 1 8

2、最底层：

7 2 1 8

3、直接复制：

7 2 1 8

4、计算第三层：

（1）数字3：

3 + max(7,2) = 10

（2）数字6：

6 + max(2,1) = 8

（3）数字9：

9 + max(1,8) = 17

（4）得到：

10 8 17

🌟九、继续往上

1、第二层：

（1）数字8：

8 + max(10,8) = 18

（2）数字4：

4 + max(8,17) = 21

2、得到：

18 21

🌟十、最后一层

1、顶部：

5 + max(18,21) = 26

2、得到：

26

3、答案：

🌟26

4、最佳路线：

5 → 4 → 9 → 8

获得：

26

颗宝石！

🌟十一、画出完整DP表

1、原图：

5 8 4 3 6 9 7 2 1 8

2、DP表：

26 18 21 10 8 17 7 2 1 8

3、同学们，看见了吗？

（1）dp[i][j]

记录的不是当前位置数字

（2）而是：

从这里开始的最大收益

🌟十二、参考代码

#include <iostream> using namespace std; int a[105][105]; int dp[105][105]; int main() { int n; cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { cin >> a[i][j]; } } // 初始化最后一层 for(int j = 1; j <= n; j++) { dp[n][j] = a[n][j]; } // 从下往上推 for(int i = n - 1; i >= 1; i--) { for(int j = 1; j <= i; j++) { dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]); } } cout << dp[1][1]; return 0; }

🌟十三、程序运行示例

1、输入：

4 5 8 4 3 6 9 7 2 1 8

2、输出：

26

🌟十四、为什么这题这么经典？

因为它让我们接触：

🌟二维DP

1、以前：

dp[i]

是一条线。

2、现在：

dp[i][j]

变成地图了！

3、以后很多题：

其实都是数字三角形变来的。

4、例如：

🗺️迷宫寻宝

🚶最短路径

🎮游戏地图

🤖机器人走格子

本质都差不多。

🌟十五、课堂挑战

🎯挑战1

求下面三角形答案：

1 2 3 4 5 6

🎯挑战2

如果要求：

最小路径和

怎么办？

提示：

把：

max(...)

改成：

min(...)

🎯挑战3

尝试输出：

整个DP表。

看看每个位置代表什么。

🌟十六、本课总结

✅数字三角形是经典二维DP

✅状态定义

dp[i][j]

表示：

从(i,j)出发到底层的最大收益

✅初始化

最后一层：

dp[n][j]=a[n][j]

✅状态转移

dp[i][j]=a[i][j]+ max(dp[i+1][j],dp[i+1][j+1])

✅计算顺序

从下往上

✅最终答案

dp[1][1]

🌟下节课预告

下一课：

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

我们将进入二维地图世界！

学习机器人如何在方格地图中寻找宝藏，并掌握大量竞赛题共用的：

🚀网格DP模型！