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+ 次浏览

启动你的职业生涯

完成课程获得认证

开始
广告