題目描述

在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角。給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？

• 0 < grid.length <= 200
• 0 < grid[0].length <= 200

題目樣例

示例

• 輸入:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

• 輸出: 12
• 解釋: 路徑 1→3→5→2→1 可以拿到最多價值的禮物

題目思考

1. 每一個格子的禮物最多價值跟什么有關?

解決方案

思路

• 分析題目, 只能向右或向下移動, 那么每個格子的最大價值只受左邊一格和上邊一格(如果存在的話)的最大價值的影響, 所以當前格子之前所能獲得的最大價值               premx 就是兩者中的較大值
• 假設 dp[r,c]代表格子(r,c)所能獲得的最大價值, 自然就有               dp[r,c] = max(dp[r-1,c], dp[r,c-1]) + grid[r][c] (r-1>=0 and c-1>=0)
• 而對于起點和左/上邊界的情況(即不能同時滿足               r-1>=0 and c-1>=0時), 有:
• 如果是左上角, 那么顯然最大價值就是本身, premx = 0
• 如果是左邊界, 那么意味著只能從上邊一格往下, 之前的最大價值就是上邊一格的最大價值, premx = grid[r - 1][c]
• 如果是上邊界, 那么意味著只能從左邊一格往右, 之前的最大價值就是左邊一格的最大價值, premx = grid[r][c - 1]
• 所以我們可以把這幾種情況統一起來, 每次遍歷到一個格子時, 將               premx 置為 0, 然后如果左邊或者上邊一格存在的話, 就更新               premx 為其中的較大值即可
• 最終結果自然就是右下角的 dp 值
• 以上就是典型的動態規劃的思想, 利用前面的計算結果來推導出當前的結果
• 另外這里還可以進行空間上的優化, 就是直接基于原數組進行修改,               grid[r][c] 累加之前計算的               premx 即可, 這樣就不需要額外 dp 矩陣了
• 下面的代碼對必要步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度 O(RC): 只需要遍歷矩陣中的每個元素即可
• 空間復雜度 O(1): 原地修改矩陣, 只使用了幾個變量

代碼

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                # 分別求左邊一格和上邊一格(如果存在的話)的最大價值, 取較大的就是當前格子之前所能取到的最大價值premx
                # premx加上當前禮物價值, 即為當前格子所能獲得的最大價值
                premx = 0
                if r - 1 >= 0:
                    premx = max(premx, grid[r - 1][c])
                if c - 1 >= 0:
                    premx = max(premx, grid[r][c - 1])
                # 原地修改矩陣, 累加premx
                grid[r][c] += premx
        # 最后結果即為右下角的值
        return grid[rows - 1][cols - 1]