GESP6级C++考试语法知识（四十五、动态规划----二维DP（二、数字三角形）
第三阶段第二课
💎《宝石矿洞探险——数字三角形》
🌟一、故事开始：神秘的宝石矿洞
1、在算法王国的地下，
有一个传说中的地方：
💎宝石矿洞💎
矿洞里堆满了宝石！
每个房间都有不同数量的宝石。
2、有一天，
小勇士阿呆接到任务：
3、🌟从矿洞顶部出发
🌟一路走到底部
🌟要收集尽可能多的宝石
4、国王说：
收集到的宝石越多，
奖励就越丰厚！
5、阿呆高兴极了：
我要成为宝石大王！6、可是矿洞很特殊。
它长这样：
5 8 4 3 6 9 7 2 1 8这就是著名的：
🌟数字三角形
🌟二、矿洞移动规则
1、阿呆从顶部开始：
52、每次只能往下一层走。
而且：
如果站在这里：
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）答案：
192、可是如果有100层呢？
路线数量会爆炸！
3、所以：
⚔️动态规划登场！
🌟四、先观察规律
1、看这个三角形：
5 8 4 3 6 9 7 2 1 82、假设：
阿呆已经来到：
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 82、如果已经到底了，
还能往哪走？
哪也不用走！
3、所以：
dp[4][1]=7 dp[4][2]=2 dp[4][3]=1 dp[4][4]=84、这就是DP的：
🌟初始化
🌟八、开始填表
1、原三角形：
5 8 4 3 6 9 7 2 1 82、最底层：
7 2 1 83、直接复制：
7 2 1 84、计算第三层：
（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) = 212、得到：
18 21🌟十、最后一层
1、顶部：
5 + max(18,21) = 262、得到：
263、答案：
🌟26
4、最佳路线：
5 → 4 → 9 → 8获得：
26颗宝石！
🌟十一、画出完整DP表
1、原图：
5 8 4 3 6 9 7 2 1 82、DP表：
26 18 21 10 8 17 7 2 1 83、同学们，看见了吗？
（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 82、输出：
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》⚔️
我们将进入二维地图世界！
学习机器人如何在方格地图中寻找宝藏，并掌握大量竞赛题共用的：