该程序查找我们可以在Python中收集的最大硬币数量

假设我们有一个2D矩阵，其中每个单元都存储一些硬币。如果我们从[0,0]开始，并且只能向右或向下移动，则必须在右下角找到可以收集的最大硬币数量。

所以，如果输入像

然后输出将为14，因为我们采用以下路径：[1、4、2、2、5]

为了解决这个问题，我们将按照以下步骤操作：

• 对于范围1至行A的r，执行

• A [r，0]：= A [r，0] + A [r-1，0]

• 对于范围1至列A的c，执行

• A [0，c]：= A [0，c] + A [0，c-1]

• 对于范围1至A大小的r，执行

• 对于范围1至A [0]大小的c，执行

• A [r，c] = A [r，c] +（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