关于leetcode:Golang力扣Leetcode剑指Offer数组47礼物的最大价值前缀和

题目：在一个 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 main

import ("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))
}

提交截图：