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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param grid int整型二维数组
 * @return int整型
 */
// 如果现在已经身处最右下角的一个格子，获取了这个礼物
// 那肯定是加上来自左边累计的最大礼物价值或来自上边累计的最大礼物价值的较大值，这样能获取的礼物价值才会更大
// 因此用 dp[i][j] 表示从左上角到第 i 行第 j 列的格子总共能获取的最大价值，因此转移方程为
// dp[i][j] = grid[i][j] + max(dp[i−1][j], dp[i][j−1])
func maxValue(grid [][]int) int {
	// write code here
	m, n := len(grid), len(grid[0])
	// 第一列只能来自上方
	for i := 1; i < m; i++ {
		grid[i][0] += grid[i-1][0]
	}
	// 第一行只能来自左边
	for i := 1; i < n; i++ {
		grid[0][i] += grid[0][i-1]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			// 将累加的礼物价值的 dp 数组直接添加在原数组 grid 中，这样可以省下一个辅助空间
			grid[i][j] += max(grid[i-1][j], grid[i][j-1])
		}
	}

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

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

	return b
}