您好,登錄后才能下訂單哦!
這篇文章主要介紹了LeetCode算法題目之如何計算禮物的最大價值,具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
在一個 m*n 的棋盤的每一格都放有一個禮物,每個禮物都有一定的價值(價值大于 0)。你可以從棋盤的左上角開始拿格子里的禮物,并每次向右或者向下移動一格、直到到達(dá)棋盤的右下角。給定一個棋盤及其上面的禮物的價值,請計算你最多能拿到多少價值的禮物?
[
[1,3,1],
[1,5,1],
[4,2,1]
]
premx
就是兩者中的較大值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
為其中的較大值即可grid[r][c]
累加之前計算的
premx
即可, 這樣就不需要額外 dp 矩陣了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):
# 分別求左邊一格和上邊一格(如果存在的話)的最大價值, 取較大的就是當(dāng)前格子之前所能取到的最大價值premx
# premx加上當(dāng)前禮物價值, 即為當(dāng)前格子所能獲得的最大價值
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
# 最后結(jié)果即為右下角的值
return grid[rows - 1][cols - 1]
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“LeetCode算法題目之如何計算禮物的最大價值”這篇文章對大家有幫助,同時也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識等著你來學(xué)習(xí)!免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。