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

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param grid int整型二维数组
 * @return int整型
 */
func maxValue(grid [][]int) int {
	vals := grid
	// 1.初始化，如 dp
	rowCount := len(vals)    // 总行数
	colCount := len(vals[0]) // 总列数
	var dp = make([][]int, rowCount)
	for i := range dp {
		dp[i] = make([]int, colCount)
	}
	// 2. 填充 dp，也就是遍历表格的每个格子，从小到大，找规律，一般大格子是由小格子计算得出
	for i := 0; i < rowCount; i++ {
		for j := 0; j < colCount; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = vals[i][j]
				continue
			}
			if i-1 < 0 {
				// 没有前一行，当前礼物的最大价值 = 前一个列格子的最大价值 + 当前格子的价值
				dp[i][j] = dp[i][j-1] + vals[i][j]
			} else if j-1 < 0 {
				// 没有前一列，当前礼物的最大价值 = 前一个行格子的最大价值 + 当前格子的价值
				dp[i][j] = dp[i-1][j] + vals[i][j]
			} else {
				// 前一列格子的最大价值 + 当前价值
				dp[i][j] = dp[i][j-1] + vals[i][j]
				// 前一行格子的最大价值 + 当前价值
				if dp[i][j] < dp[i-1][j]+vals[i][j] {
					dp[i][j] = dp[i-1][j] + vals[i][j]
				}
			}
		}
	}
	// 3. 考虑临界点，如下标异常
	// 4. 返回结果
	return dp[rowCount-1][colCount-1]
	// 5. 优化空间和时间复杂度

}