题目：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
链接： 力扣Leetcode—剑指Offer—数组—47.礼物的最大价值.
示例 1：
输入:思路：用前缀和的方式处理，用双重for循环，如下：
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
- 外层for从第2行开始，最后1行结束
- 内层for从第2列开始，最后1列结束
- 比较左方和上方的值，并取其中较大者，加到当前位置的值上
- 返回最右下角的值
[1,3,1]把 第1行 和 第1列 分别用前缀和的方式处理，得到：
[1,5,1]
[4,2,1]
[1,4,5]再遍历剩余位置，也就是从第二行第二列开始，取当前位置的上边和左边中的较大者，加到当前位置的值上：
[2,5,1]
[6,2,1]
[1,4,5]加粗部分为所要遍历的位置
[2,5,1]
[6,2,1]
- 先从加粗的5开始(第2行，第2列)
- 取左边(2)和上边(4)的较大者(4)
- 加到当前位置的值(5)上
[1,4,5]重复上述步骤，依次得到:
[2,9,1]
[6,2,1]
已处理第2行，第3列 (1 + max(9, 5) = 1 + 9 = 10)：
[1,4,5]已处理第3行，第2列 (2 + max(9, 6) = 2 + 9 = 11)：
[2,9,10]
[6,2,1]
[1,4,5]已处理第3行，第3列 (1 + max(11, 10) = 1 + 11 = 12)：
[2,9,10]
[6,11,1]
[1,4,5]全部处理完毕，返回最右下角的值(12)
[2,9,10]
[6,11,12]
Go代码如下：
package mainimport (
"fmt"
)func max(a, b int) int {
if a >= b {
return a
}
return b
}func maxValue(grid [][]int) int {
row := len(grid) - 1// 列
col := len(grid[0]) - 1 // 行
for i := 0;
i <= row;
i++ {
for j := 0;
j <= col;
j++ {
//把第1行 和 第1列 分别用前缀和的方式处理
if i == 0 && j == 0 {
continue
}
if i == 0 {
grid[i][j] += grid[i][j-1]
continue
}
if j == 0 {
grid[i][j] += grid[i-1][j]
continue
}
//遍历剩余位置，取当前位置的上边和左边中的较大者，加到当前位置的值上
grid[i][j] += max(grid[i-1][j], grid[i][j-1])
}
}
//最后一位为累计最大值
return grid[row][col]
}func main() {
a := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}
fmt.Println(maxValue(a))
}
提交截图：
![[Golang]力扣Leetcode—剑指Offer—数组—47.礼物的最大价值（前缀和）](https://img.it610.com/image/info9/ab234d66886242829b15d1c9834895fd.jpg)
文章图片
