第三阶段第四课《黄金矿工大赛——网格最大价值DP》一、故事开始黄金矿工大赛1、在算法王国里一年一度的⛏️黄金矿工大赛开始啦2、参赛选手们来到一座巨大的黄金迷宫。地图长这样1 3 2 5 4 1 2 8 63、每个格子里都藏着黄金例如5表示这里有5块黄金。4、比赛规则矿工从左上角出发目标到达右下角终点。并且一路收集尽可能多的黄金5、但是矿工行动不自由。只能→ 向右 ↓ 向下不能← ↑6、国王的问题来了怎样走才能拿到最多黄金二、先用眼睛观察1、地图1 3 2 5 4 1 2 8 62、路线11 → 3 → 2 → 1 → 6黄金133、路线21 → 5 → 4 → 8 → 6黄金244、明显第二条更赚钱5、可是如果地图变成100 × 100怎么办不可能把所有路线都试一遍于是⚔️DP登场三、和上一课有什么区别1、上一课机器人迷宫寻宝求有多少种走法2、状态转移上面 左边3、因为统计路线数量。4、今天求的是最大价值5、所以思路完全变了四、定义状态1、定义dp[i][j]表示2、从起点走到(i,j)能够获得的最大黄金数例如dp[2][3]表示走到第二行第三列时最多能拿多少黄金。五、来到一个格子1、例如?位置(2,2)2、矿工从哪里来只能上面或者左边3、例如4这个格子价值4。4、假设1上面最好路线102左边最好路线83矿工会怎么选当然选10那条路4因为黄金更多5然后再加上当前格子的黄金。得到10 4 14六、状态转移公式1、于是当前位置价值 上面和左边中的较大值2、公式来了dp[i][j]a[i][j] max(dp[i-1][j],dp[i][j-1])这就是本课最重要的公式七、初始化1、看起点(1,1)这里只有一种情况直接站在这里。所以dp[1][1]a[1][1];2、例如1那么dp[1][1]1;八、先处理第一行1、地图1 3 2 5 4 1 2 8 62、机器人只能一直向右。1所以dp[1][2] 13 42继续dp[1][3] 42 63第一行1 4 6九、处理第一列1、第一列1 5 22、只能一直向下。1所以dp[2][1] 15 62继续dp[3][1] 62 83第一列1 6 8十、开始填表1、原地图1 3 2 5 4 1 2 8 62、DP表1先填边界1 4 6 6 82计算(2,2)3价值44上面45左边66选大的67得到6 4 103、所以dp[2][2]10;十一、继续填1、位置(2,3)1价值12上面63左边104取最大105得到112、继续位置(3,2)1价值82上面103左边84得到183、最后位置(3,3)1价值62上面113左边184得到24十二、最终DP表1 4 6 6 10 11 8 18 24终点24答案24最佳路线1 → 5 → 4 → 8 → 6十三、参考代码#include iostream using namespace std; int a[105][105]; int dp[105][105]; int main() { int n,m; cin n m; for(int i1;in;i) { for(int j1;jm;j) { cin a[i][j]; } } dp[1][1]a[1][1]; // 第一行 for(int j2;jm;j) { dp[1][j] dp[1][j-1] a[1][j]; } // 第一列 for(int i2;in;i) { dp[i][1] dp[i-1][1] a[i][1]; } // 其余位置 for(int i2;in;i) { for(int j2;jm;j) { dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]; } } coutdp[n][m]; return 0; }十四、如何输出最佳路线1、很多同学会问我知道答案是24。可是到底怎么走的2、其实很简单。1从终点开始倒推。2例如24来自18还是113选大的那个。4一路往前找。5最后就能找到1 ↓ 5 → 4 ↓ 8 → 63、这叫路径还原以后会专门学习。十五、课堂挑战挑战1计算1 2 3 4最大价值是多少挑战2计算5 1 1 2 10 1 1 1 20最佳路线价值是多少挑战3如果格子里有陷阱-5怎么办提示公式不用变DP仍然成立挑战4如果允许→ ↓ ↘三种方向移动。状态转移如何修改提示多比较一个方向。十六、和上一课对比1、上一课求方案数公式dp[i][j]dp[i-1][j]dp[i][j-1]2、这一课求最大价值公式dp[i][j]a[i][j] max(dp[i-1][j],dp[i][j-1])3、这两个题长得特别像1但一个是统计数量2一个是求最优解4、这就是动态规划中最重要的思想之一状态定义不同转移公式就不同十七、本课总结1、✅ 状态定义dp[i][j]表示到达(i,j)时能获得的最大黄金数。2、✅ 状态转移当前位置黄金上方和左方中的较大值。3、✅ 初始化第一行只能向右。第一列只能向下。4、✅ 最终答案dp[n][m]5、✅ 这是最经典的二维最优路径DP下节课预告下一课⚔️《超级背包仓库——01背包DP》⚔️从下一课开始我们将进入动态规划最著名、最经典、最重要的一大门派背包DP
GESP6级C++考试语法知识（四十七、动态规划----二维DP（四、网格最大价值DP）
第三阶段第四课《黄金矿工大赛——网格最大价值DP》一、故事开始黄金矿工大赛1、在算法王国里一年一度的⛏️黄金矿工大赛开始啦2、参赛选手们来到一座巨大的黄金迷宫。地图长这样1 3 2 5 4 1 2 8 63、每个格子里都藏着黄金例如5表示这里有5块黄金。4、比赛规则矿工从左上角出发目标到达右下角终点。并且一路收集尽可能多的黄金5、但是矿工行动不自由。只能→ 向右 ↓ 向下不能← ↑6、国王的问题来了怎样走才能拿到最多黄金二、先用眼睛观察1、地图1 3 2 5 4 1 2 8 62、路线11 → 3 → 2 → 1 → 6黄金133、路线21 → 5 → 4 → 8 → 6黄金244、明显第二条更赚钱5、可是如果地图变成100 × 100怎么办不可能把所有路线都试一遍于是⚔️DP登场三、和上一课有什么区别1、上一课机器人迷宫寻宝求有多少种走法2、状态转移上面 左边3、因为统计路线数量。4、今天求的是最大价值5、所以思路完全变了四、定义状态1、定义dp[i][j]表示2、从起点走到(i,j)能够获得的最大黄金数例如dp[2][3]表示走到第二行第三列时最多能拿多少黄金。五、来到一个格子1、例如?位置(2,2)2、矿工从哪里来只能上面或者左边3、例如4这个格子价值4。4、假设1上面最好路线102左边最好路线83矿工会怎么选当然选10那条路4因为黄金更多5然后再加上当前格子的黄金。得到10 4 14六、状态转移公式1、于是当前位置价值 上面和左边中的较大值2、公式来了dp[i][j]a[i][j] max(dp[i-1][j],dp[i][j-1])这就是本课最重要的公式七、初始化1、看起点(1,1)这里只有一种情况直接站在这里。所以dp[1][1]a[1][1];2、例如1那么dp[1][1]1;八、先处理第一行1、地图1 3 2 5 4 1 2 8 62、机器人只能一直向右。1所以dp[1][2] 13 42继续dp[1][3] 42 63第一行1 4 6九、处理第一列1、第一列1 5 22、只能一直向下。1所以dp[2][1] 15 62继续dp[3][1] 62 83第一列1 6 8十、开始填表1、原地图1 3 2 5 4 1 2 8 62、DP表1先填边界1 4 6 6 82计算(2,2)3价值44上面45左边66选大的67得到6 4 103、所以dp[2][2]10;十一、继续填1、位置(2,3)1价值12上面63左边104取最大105得到112、继续位置(3,2)1价值82上面103左边84得到183、最后位置(3,3)1价值62上面113左边184得到24十二、最终DP表1 4 6 6 10 11 8 18 24终点24答案24最佳路线1 → 5 → 4 → 8 → 6十三、参考代码#include iostream using namespace std; int a[105][105]; int dp[105][105]; int main() { int n,m; cin n m; for(int i1;in;i) { for(int j1;jm;j) { cin a[i][j]; } } dp[1][1]a[1][1]; // 第一行 for(int j2;jm;j) { dp[1][j] dp[1][j-1] a[1][j]; } // 第一列 for(int i2;in;i) { dp[i][1] dp[i-1][1] a[i][1]; } // 其余位置 for(int i2;in;i) { for(int j2;jm;j) { dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]; } } coutdp[n][m]; return 0; }十四、如何输出最佳路线1、很多同学会问我知道答案是24。可是到底怎么走的2、其实很简单。1从终点开始倒推。2例如24来自18还是113选大的那个。4一路往前找。5最后就能找到1 ↓ 5 → 4 ↓ 8 → 63、这叫路径还原以后会专门学习。十五、课堂挑战挑战1计算1 2 3 4最大价值是多少挑战2计算5 1 1 2 10 1 1 1 20最佳路线价值是多少挑战3如果格子里有陷阱-5怎么办提示公式不用变DP仍然成立挑战4如果允许→ ↓ ↘三种方向移动。状态转移如何修改提示多比较一个方向。十六、和上一课对比1、上一课求方案数公式dp[i][j]dp[i-1][j]dp[i][j-1]2、这一课求最大价值公式dp[i][j]a[i][j] max(dp[i-1][j],dp[i][j-1])3、这两个题长得特别像1但一个是统计数量2一个是求最优解4、这就是动态规划中最重要的思想之一状态定义不同转移公式就不同十七、本课总结1、✅ 状态定义dp[i][j]表示到达(i,j)时能获得的最大黄金数。2、✅ 状态转移当前位置黄金上方和左方中的较大值。3、✅ 初始化第一行只能向右。第一列只能向下。4、✅ 最终答案dp[n][m]5、✅ 这是最经典的二维最优路径DP下节课预告下一课⚔️《超级背包仓库——01背包DP》⚔️从下一课开始我们将进入动态规划最著名、最经典、最重要的一大门派背包DP
