第三阶段第二课《宝石矿洞探险——数字三角形》一、故事开始神秘的宝石矿洞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 91路线15 → 8 → 3宝石162路线25 → 8 → 6宝石193路线35 → 4 → 6宝石154路线45 → 4 → 9宝石185答案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 82数字6的位置dp[3][2]表示3从6开始走到底部最多能得到多少宝石。六、最重要的一步1、来到61下面有两个选择2或者12阿呆会怎么选当然选宝石更多的路所以当前位置价值 下面两条路中的最大值2、状态转移公式来了dp[i][j] a[i][j] max(dp[i1][j],dp[i1][j1])这句话非常重要意思是当前位置宝石左下路线最大收益和右下路线最大收益中的较大者七、为什么我们要从下面开始算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数字33 max(7,2) 102数字66 max(2,1) 83数字99 max(1,8) 174得到10 8 17九、继续往上1、第二层1数字88 max(10,8) 182数字44 max(8,17) 212、得到18 21十、最后一层1、顶部5 max(18,21) 262、得到263、答案264、最佳路线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、同学们看见了吗1dp[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[i1][j], dp[i1][j1]); } } cout dp[1][1]; return 0; }十三、程序运行示例1、输入4 5 8 4 3 6 9 7 2 1 82、输出26十四、为什么这题这么经典因为它让我们接触二维DP1、以前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[i1][j],dp[i1][j1])✅计算顺序从下往上✅最终答案dp[1][1]下节课预告下一课⚔️《机器人迷宫寻宝——网格路径DP》⚔️我们将进入二维地图世界学习机器人如何在方格地图中寻找宝藏并掌握大量竞赛题共用的网格DP模型
GESP6级C++考试语法知识（四十五、动态规划----二维DP（二、数字三角形）
发布时间：2026/6/2 17:05:11
第三阶段第二课《宝石矿洞探险——数字三角形》一、故事开始神秘的宝石矿洞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 91路线15 → 8 → 3宝石162路线25 → 8 → 6宝石193路线35 → 4 → 6宝石154路线45 → 4 → 9宝石185答案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 82数字6的位置dp[3][2]表示3从6开始走到底部最多能得到多少宝石。六、最重要的一步1、来到61下面有两个选择2或者12阿呆会怎么选当然选宝石更多的路所以当前位置价值 下面两条路中的最大值2、状态转移公式来了dp[i][j] a[i][j] max(dp[i1][j],dp[i1][j1])这句话非常重要意思是当前位置宝石左下路线最大收益和右下路线最大收益中的较大者七、为什么我们要从下面开始算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数字33 max(7,2) 102数字66 max(2,1) 83数字99 max(1,8) 174得到10 8 17九、继续往上1、第二层1数字88 max(10,8) 182数字44 max(8,17) 212、得到18 21十、最后一层1、顶部5 max(18,21) 262、得到263、答案264、最佳路线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、同学们看见了吗1dp[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[i1][j], dp[i1][j1]); } } cout dp[1][1]; return 0; }十三、程序运行示例1、输入4 5 8 4 3 6 9 7 2 1 82、输出26十四、为什么这题这么经典因为它让我们接触二维DP1、以前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[i1][j],dp[i1][j1])✅计算顺序从下往上✅最终答案dp[1][1]下节课预告下一课⚔️《机器人迷宫寻宝——网格路径DP》⚔️我们将进入二维地图世界学习机器人如何在方格地图中寻找宝藏并掌握大量竞赛题共用的网格DP模型
