leetcode --- 礼物的最大价值（DP）

礼物的最大价值
leetcode-golang

1.PNG

思路

设(i,j)位置能拿到的最多价值为maxVal [i] [j]，因为每次只能向右或向下移动一格

1. maxVal[i][j] = max(maxVal [i-1] [j], maxVal [i] [j-1])

排除 i-1, j-1 越界的情况

代码

func maxValue(grid [][]int) int {
    maxVal := make([][]int, len(grid))
    for i := 0;i < len(grid);i++ {
        maxVal[i] = make([]int, len(grid))
    }
    copy(maxVal, grid)

    for i := 0;i < len(maxVal);i++ {
        max := 0
        for j := 0;j < len(maxVal[i]);j++ {
            // 上面
            if i - 1 >= 0 && max < maxVal[i-1][j] {
                max = maxVal[i-1][j]
            }
            // 左边
            if j - 1 >= 0 && max < maxVal[i][j-1] {
                max = maxVal[i][j-1]
            }

            maxVal[i][j] += max
        }
    }

    i1, i2 := len(maxVal) - 1, len(maxVal[0]) - 1
    return maxVal[i1][i2]
}

有疑问加站长微信联系（非本文作者）