题解 | #礼物的最大价值#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
*/
func maxValue( grid [][]int ) int {
    // write code here
    m, n := len(grid), len(grid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    dp[0][0] = grid[0][0]
    // 初始化第一行 
    for i := 1; i < n; i++  {
        dp[0][i] = grid[0][i] + dp[0][i-1]
    }
    // 初始化第一列
    for i := 1; i < m; i++ {
        dp[i][0] = grid[i][0] + dp[i-1][0]
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ { // 两个方向取最大
            dp[i][j] = max(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
        }
    }

    return dp[m-1][n-1]
}

func max(a, b int) int {
    if a < b {
        return b
    }

    return a
}