题目：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有肯定的价值（价值大于 0）。你能够从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下挪动一格、直到达到棋盘的右下角。给定一个棋盘及其下面的礼物的价值，请计算你最多能拿到多少价值的礼物？
链接： 力扣Leetcode—剑指Offer—数组—47.礼物的最大价值.
示例 1：
输出:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输入: 12
解释: 门路 1→3→5→2→1 能够拿到最多价值的礼物
思路：用前缀和的形式解决，用双重for循环，如下：
- 外层for从第2行开始，最初1行完结
- 内层for从第2列开始，最初1列完结
- 比拟左方和上方的值，并取其中较大者，加到以后地位的值上
- 返回最右下角的值
就拿上面的例子来讲：
[1,3,1]
[1,5,1]
[4,2,1]
把 第1行 和 第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)上
失去第2行，第2列：
[1,4,5]
[2,9,1]
[6,2,1]
反复上述步骤，顺次失去:
已解决第2行，第3列 (1 + max(9, 5) = 1 + 9 = 10)：
[1,4,5]
[2,9,10]
[6,2,1]
已解决第3行，第2列 (2 + max(9, 6) = 2 + 9 = 11)：
[1,4,5]
[2,9,10]
[6,11,1]
已解决第3行，第3列 (1 + max(11, 10) = 1 + 11 = 12)：
[1,4,5]
[2,9,10]
[6,11,12]
全副处理完毕，返回最右下角的值(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))}提交截图：