# 题目链接
# 题目描述
在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
1
2
3
4
2
3
4
礼物的最大价值为 1+12+5+7+7+16+5=53。
# 解题思路
常规动态规划思路 找状态：每一步礼物的最大值 转移方程：dp[i][j]=grid[i-1][j-1]+max(dp[i][j-1],dp[i-1][j])
func maxValue(grid [][]int) int {
dp:=make([][]int,len(grid)+1)
for i:=0;i<=len(grid);i++{
dp[i] = make([]int,len(grid[0])+1)
}
max:=func(x,y int)int{
if x<y{
return y
}
return x
}
for i:=1;i<len(dp);i++{
for j:=1;j<len(dp[i]);j++{
dp[i][j]=grid[i-1][j-1]+max(dp[i][j-1],dp[i-1][j])
}
}
return dp[len(grid)][len(grid[0])]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22