2369. 挖矿
1000ms
256MB
简单
动态规划
Dynamic Programming
题目描述
在一个大小为 $n \times m$ 的网格星空图纸中，每个格子内都标记了该区域的可开采矿石储量。
开采飞船从图纸的左上角入口 $(1, 1)$ 进入这片星域，且在移动过程中只能向右或者向下移动，最终从图纸的右下角 $(n, m)$ 出口离开。
请编写程序，寻找一条可以开采矿石最多的路径，并输出该路径可开采的矿石总量。
输入格式
- 第一行包含两个以空格隔开的正整数 $n$ 和 $m$ ($1 \le n, m \le 30$)，分别表示网格图纸的行数和列数。
- 接下来 $n$ 行，每行包含 $m$ 个以空格隔开的非负整数 $k$ ($0 \le k \le 3$)，表示每个格子区域内的矿石储量。
输出格式
- 输出一个整数，表示可开采的最大矿石数量。
样例 1
输入 (Input)
3 4 1 2 2 3 2 1 1 0 2 0 3 1
输出 (Output)
10
样例说明
- **样例说明**：
在 $3 \times 4$ 的矩阵中，最佳开采路径如下：
- 起点 $(1,1)$ 开始，开采量为 1；
- 向右移动至 $(1,2)$，累计开采量为 $1 + 2 = 3$；
- 向右移动至 $(1,3)$，累计开采量为 $3 + 2 = 5$；
- 向下移动至 $(2,3)$，累计开采量为 $5 + 1 = 6$；
- 向下移动至 $(3,3)$，累计开采量为 $6 + 3 = 9$；
- 向右移动至终点 $(3,4)$，最终累计开采量为 $9 + 1 = 10$。
- 对于 $100\%$ 的数据：$1 \le n, m \le 30$，$0 \le k \le 3$。
- **算法提示**：
本题可通过**动态规划（DP）**求解。
1. 设 $dp[i][j]$ 表示到达网格中坐标 $(i, j)$ 位置时所能获得的最大矿石数。
2. 由于飞船只能由上方或左方格子移动而来，因此状态转移方程为：
$$dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j]$$
3. 边界条件：
- 起点位置 $dp[0][0] = grid[0][0]$。
- 第一行的每个格子只能由其左侧格子到达：$dp[0][j] = dp[0][j-1] + grid[0][j]$。
- 第一列的每个格子只能由其上方格子到达：$dp[i][0] = dp[i-1][0] + grid[i][0]$。
4. 最终 $dp[n-1][m-1]$ 即为答案。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功