第三阶段第四课
💰《黄金矿工大赛——网格最大价值DP》
🌟一、故事开始：黄金矿工大赛
1、在算法王国里，
一年一度的：
⛏️黄金矿工大赛
开始啦！
2、参赛选手们来到一座巨大的黄金迷宫。
地图长这样：
1 3 2
5 4 1
2 8 6
3、每个格子里，
都藏着黄金！
例如：
5
表示：
这里有5块黄金。
4、比赛规则：
矿工从左上角出发：
🚶
目标：
到达右下角终点。
并且：
🌟一路收集尽可能多的黄金！
5、但是矿工行动不自由。
只能：
→ 向右
↓
向下
不能：
←
↑
6、国王的问题来了：
🌟怎样走才能拿到最多黄金？
🌟二、先用眼睛观察
1、地图：
1 3 2
5 4 1
2 8 6
2、路线1：
1 → 3 → 2 → 1 → 6
黄金：
13
3、路线2：
1 → 5 → 4 → 8 → 6
黄金：
24
4、明显：
第二条更赚钱！
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）上面最好路线：
10
（2）左边最好路线：
8
（3）矿工会怎么选？
当然选：
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 6
2、机器人只能一直向右。
（1）所以：
dp[1][2] = 1+3 = 4
（2）继续：
dp[1][3] = 4+2 = 6
（3）第一行：
1 4 6
🌟九、处理第一列
1、第一列：
1
5
2
2、只能一直向下。
（1）所以：
dp[2][1]
=
1+5
=
6
（2）继续：
dp[3][1]
=
6+2
=
8
（3）第一列：
1
6
8
🌟十、开始填表
1、原地图：
1 3 2
5 4 1
2 8 6
2、DP表：
（1）先填边界：
1 4 6
6
8
（2）计算：
(2,2)
（3）价值：
4
（4）上面：
4
（5）左边：
6
（6）选大的：
6
（7）得到：
6 + 4 = 10
3、所以：
dp[2][2]=10;
🌟十一、继续填
1、位置：
(2,3)
（1）价值：
1
（2）上面：
6
（3）左边：
10
（4）取最大：
10
（5）得到：
11
2、继续位置：
(3,2)
（1）价值：
8
（2）上面：
10
（3）左边：
8
（4）得到：
18
3、最后位置：
(3,3)
（1）价值：
6
（2）上面：
11
（3）左边：
18
（4）得到：
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 i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> a[i][j];
}
}
dp[1][1]=a[1][1];
// 第一行
for(int j=2;j<=m;j++)
{
dp[1][j]
=
dp[1][j-1]
+
a[1][j];
}
// 第一列
for(int i=2;i<=n;i++)
{
dp[i][1]
=
dp[i-1][1]
+
a[i][1];
}
// 其余位置
for(int i=2;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
dp[i][j]
=
max(dp[i-1][j],
dp[i][j-1])
+
a[i][j];
}
}
cout<<dp[n][m];
return 0;
}
🌟十四、如何输出最佳路线？
1、很多同学会问：
我知道答案是24。
可是：
🌟到底怎么走的？
2、其实很简单。
（1）从终点开始倒推。
（2）例如：
24
来自：
18
还是：
11
？
（3）选大的那个。
（4）一路往前找。
（5）最后就能找到：
1
↓
5
→
4
↓
8
→
6
3、这叫：
🌟路径还原
以后会专门学习。
🌟十五、课堂挑战
🎯挑战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》⚔️
从下一课开始，
我们将进入动态规划最著名、最经典、最重要的一大门派：
