資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究Python程式：查詢可收集到的最大硬幣數量
假設我們有一個二維矩陣，每個單元格儲存一些硬幣。如果我們從[0,0]開始，只能向右或向下移動，我們必須找到到達右下角可以收集到的最大硬幣數量。
因此，如果輸入如下所示：
| 1 | 4 | 2 | 2 |
| 0 | 0 | 0 | 5 |
那麼輸出將是14，因為我們選擇路徑：[1, 4, 2, 2, 5]
為了解決這個問題，我們將遵循以下步驟：
對於 r 從 1 到 A 的行數，執行：
A[r, 0] := A[r, 0] + A[r-1, 0]
對於 c 從 1 到 A 的列數，執行：
A[0, c] := A[0, c] + A[0, c-1]
對於 r 從 1 到 A 的大小，執行：
對於 c 從 1 到 A[0] 的大小，執行：
A[r, c] = A[r, c] + max(A[r-1, c], A[r, c-1])
返回 A 的右下角的值
讓我們看看下面的實現來更好地理解：
示例
class Solution: def solve(self, A): for r in range(1, len(A)): A[r][0] += A[r-1][0] for c in range(1, len(A[0])): A[0][c] += A[0][c-1] for r in range(1, len(A)): for c in range(1, len(A[0])): A[r][c] += max(A[r-1][c], A[r][c-1]) return A[-1][-1] ob = Solution() matrix = [ [1, 4, 2, 2], [6, 0, 0, 5] ] print(ob.solve(matrix))
輸入
matrix = [ [1, 4, 2, 2], [6, 0, 0, 5] ]
輸出
14
更新於：2020年10月5日
1K+ 次瀏覽
廣告