1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// @Title: 礼物的最大价值 (礼物的最大价值 LCOF)
// @Author: 15816537946@163.com
// @Date: 2022-02-13 13:51:23
// @Runtime: 0 ms
// @Memory: 3.7 MB
// var dirs = []struct{x,y int}{{1,0},{-1,0},{0,1},{0,-1}}

func maxValue(grid [][]int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }

    m,n:= len(grid),len(grid[0])
    for i:=1;i<m;i++ {
        grid[i][0] +=  grid[i-1][0]
    }
    for j:=1;j<n;j++ {
        grid[0][j] += grid[0][j-1]
    }

    for i:=1;i<m;i++ {
        for j:=1;j<n;j++ {
            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
}