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

package main

//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param grid int整型二维数组
 * @return int整型
 */
func maxValue(grid [][]int) int {
	// write code here
	//动态规划
    //需要求从矩阵左上到右下的累计最大值
    //分割问题，每个格子的累计最大值必然是本格+上一个格子或左一格中较大的那个值
	//用dp[m][n]来存储每个格子的累计最大价值
    //最后右下角的dp值就是答案
	m, n := len(grid), len(grid[0])
	dp := make([][]int, m)

	//记得对数组的2维初始化
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
		dp[i][0] += grid[i][0]
	}
    
    //计算每个格子的累计最大价值
    //有3类情况，没有上、没有左、有上有左
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i > 0 && j > 0 {
                dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
            } else if i == 0 && j > 0 {
                dp[i][j] = grid[i][j] + dp[i][j-1]
            } else if i > 0 && j == 0 {
                dp[i][j] = grid[i][j] + dp[i-1][j]
            }
        }
    }
     
    return dp[m-1][n-1]
}

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