47. 礼物的最大价值.md

解题思路

动态规划

dp[i][j] 代表当前位置能拿到的礼物最大价值 当前最大价值 = 上一步最大价值 + 当前价值

func maxValue(grid [][]int) int {
    dp := make([][]int, len(grid)+1)
    for i := range dp {
        dp[i] = make([]int, len(grid[0])+1)
    }
    for i := 1; i <= len(grid); i++ {
        for j := 1; j <= len(grid[0]); j++ {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]
        }
    }
    return dp[len(grid)][len(grid[0])]
}

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