LeetCode 剑指 Offer 47. 礼物的最大价值
题目描述
题意分析
从网格左上角出发，每次只能向右或向下移动一格，直到右下角，沿途经过的格子都可以拿到礼物。每个礼物价值大于零，求一条路径能取得的最大价值总和，起点和终点也计入。
只能选择一条连续路径，不能同时收集两条分支上的礼物。每次只能来自上方或左方，因此当前格子的最优结果取决于这两个相邻前驱。
解法：一维动态规划
核心思路
[!blue]
到达当前格子的最后一步只能是从上面向下，或从左边向右。无论最后一步来自哪一边，都应沿用到达那个前驱的最大价值；若前缀路径还可以更好，当前整条路径也能随之改善。因此当前最优值等于两个前驱中的较大值，再加当前礼物价值。
按行从上到下、每行从左到右计算，两个前驱都已准备好。用一维数组压缩状态：更新列
j之前，dp[j]仍是上一行同列的最优值；dp[j - 1]已经更新，表示当前行左侧的最优值。读取这两个值后覆盖dp[j]，就得到当前格子的答案。第一列没有左侧前驱，令
left = 0；第一行的上方状态也初始为零。因为礼物价值为正，边界上已经形成的合法路径会优于这个零，故第一行自然从左侧累积，第一列自然从上方累积。左上角两个前驱都为零，恰好得到它自己的价值。每个格子完成后，一维数组左边部分表示当前行，尚未处理的部分表示上一行。最后一行更新结束时，最后一列就是到右下角的最大价值；原网格无需修改。
解题步骤
- 创建长度为列数的零数组
dp。- 从第一行到最后一行处理，每行都从左向右。
- 取更新前的
dp[j]作为上方值，取已经更新的dp[j - 1]作为左方值；第一列左方值为零。- 将两者较大值加上
grid[i][j]，覆盖dp[j]。- 全部处理完成后返回最后一列的状态。
代码实现
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int left = 0;
if (j > 0) {
// 左侧已经更新，表示当前行的最优路径。
left = dp[j - 1];
}
// 覆盖前保存上一行同列的旧值。
int up = dp[j];
dp[j] = Math.max(left, up) + grid[i][j];
}
}
return dp[n - 1];
}
}
func maxValue(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([]int, n)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
left := 0
if j > 0 {
// 左侧已经更新，表示当前行的最优路径。
left = dp[j-1]
}
// 覆盖前保存上一行同列的旧值。
up := dp[j]
if left > up {
dp[j] = left + grid[i][j]
} else {
dp[j] = up + grid[i][j]
}
}
}
return dp[n-1]
}
复杂度分析
设网格有 $m$ 行、$n$ 列。
- 时间复杂度：$O(mn)$，每个格子只进行一次常数时间转移。
- 辅助空间复杂度：$O(n)$，只保存一行状态，输入网格不修改。
关键点总结
[!green]
- 最后一步只有上、左两种来源，取较大前缀而不是把两个分支相加。
- 一维数组同时承载上一行与当前行，读取方向决定状态含义。
- 正价值保证零初始化能统一处理起点和首行、首列。
易错点总结
[!yellow]
- 从右到左更新会读到上一行的左侧状态，无法表达当前行的左方前驱。
- 使用已经覆盖的当前值作为上方状态，会把不同阶段的数据混在一起。
- 将上方和左方路径相加，会收集同一条路径无法同时经过的分支，还可能重复计数。
- 边界以零代替不存在的前驱依赖本题的正价值条件，不能直接照搬到允许负值的同类问题。
- 行数和列数要分开，一维状态长度对应列数，最终读取的是最后一列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 64. 最小路径和 | 中等 | 移动方向相同，原题取最小路径和，本题取最大路径和，状态取优方向不同。 |
| 1301. 最大得分的路径数目 | 困难 | 同样计算网格最优得分，原题还需统计最优路径数量且可对角移动，本题只取最大价值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！