HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序来查找我们可以收集的最大硬币数量

pythonserver side programmingprogramming更新于 2026/1/10 11:56:17

假设我们有一个 2D 矩阵，其中每个单元存储一些硬币。如果我们从 [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] + (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

相关文章

有用资源

打印 下一节:用 Python 编写一个程序，计算将所有单元格变成相同颜色所需的操作次数 ❯❮ 上一节:用 Python 编写程序，查找二叉树中任意路径的最大和