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

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

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

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

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

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

所以，如果输入像

那么输出将为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