47.md

礼物的最大价值

题目

在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 如输入这样的一个二维数组， [ [1,3,1], [1,5,1], [4,2,1] ] 那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12

思路

• 每次只能向下或者向上走一格，所以对于每一个单元格来说，只能通过其左边的单元格或者上边的单元格到达，因此dp数组保存走到当前grid单元格能够得到的最大价值
• 对于第i行第j列的格子而言，走到这个单元格所能得到的最大值为 dp[同列上一行] 与 dp[同行前一列] 中最大值加上本格的值
• 递推公式： max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

实现

package main

import "fmt"

// 礼物的最大价值
func Run() {
	var grid [][]int
	row := []int{1, 3, 1}
	grid = append(grid, row)
	row = []int{1, 5, 1}
	grid = append(grid, row)
	row = []int{4, 2, 1}
	grid = append(grid, row)
	res := maxValue(grid)
	fmt.Println(res)
}

func maxValue(grid [][]int) int {
	// 初始化最上一行
	for j := 1; j < len(grid[0]); j++ {
		grid[0][j] = grid[0][j-1] + grid[0][j]
	}
	// 初始化最左一列
	for i := 1; i < len(grid); i++ {
		grid[i][0] = grid[i-1][0] + grid[i][0]
	}
	// 逐列
	for i := 1; i < len(grid); i++ {
		// 逐行
		for j := 1; j < len(grid[0]); j++ {
			grid[i][j] = max(grid[i-1][j], grid[i][j-1]) + grid[i][j]
		}
	}
	return grid[len(grid)-1][len(grid[0])-1]
}

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