找出可以在Python中收集的最大硬币数量的问题

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个二维矩阵，其中的单元代表其中的硬币数量。我们有两个朋友来收集硬币，它们分别位于开始时的左上角和右上角。他们遵循以下规则：

  • 硬币收集器可以从单元格(i,j)移至单元格（i + 1，j-1），（i + 1，j）或（i + 1，j + 1）。

  • 到达牢房后，他们会收集所有可用硬币，使牢房变空。

  • 收藏家可以选择留在一个牢房，但是任何一个牢房中的硬币只能收集一次。

我们必须找到可以收集的最大硬币数量。

所以，如果输入像

0410
3140
2511
3000

那么输出将为17。

为了解决这个问题，我们将遵循以下步骤-

  • A：=输入矩阵

  • R：= A的行数

  • C：= A的列数

  • 定义一个功能dp()。这将需要r，c1，c2

    • 对于[c2 − 1，c2，c2 + 1]中的每个nc2，执行

    • ans：= ans和（base + dp（r + 1，nc1，nc2））的最大值

    • 如果0 <= nc1 <C和0 <= nc2 <C，则

    • 返回0

    • 如果r与R相同，则

    • ans：= A [r，c1] +（如果c1不等于c2，则1否则为0）* A [r，c2]

    • 基本：= ans

    • 对于[c1 − 1，c1，c1 + 1]中的每个nc1，执行

    • 返回ans

    • 返回dp（0，0，C − 1）

    让我们看下面的实现以更好地理解-

    示例

    class Solution:
       def solve(self, A):
          R, C = len(A), len(A[0])
          def dp(r, c1, c2):
             if r == R:
                return 0
             ans = base = A[r][c1] + (c1 != c2) * A[r][c2]
             for nc1 in [c1 − 1, c1, c1 + 1]:
                for nc2 in [c2 − 1, c2, c2 + 1]:
                   if 0 <= nc1 < C and 0 <= nc2 < C:
                      ans = max(ans, base + dp(r + 1, nc1, nc2))
             return ans
          return dp(0, 0, C − 1)
    ob = Solution()
    print(ob.solve([
       [0, 4, 1, 0],
       [3, 1, 4, 0],
       [2, 5, 1, 1],
       [3, 0, 0, 0]
    ]))

    输入值

    [
       [0, 4, 1, 0],
       [3, 1, 4, 0],
       [2, 5, 1, 1],
       [3, 0, 0, 0]
    ]
    输出结果
    17

    以上是 找出可以在Python中收集的最大硬币数量的问题 的全部内容， 来源链接： utcz.com/z/315924.html

    回到顶部