Pythonで収集できるコインの最大数を見つけるためのプログラム

各セルにいくつかのコインが格納されている2Dマトリックスがあるとします。 [0,0]から始めて、右または下にしか移動できない場合、右下隅で収集できるコインの最大数を見つける必要があります。

したがって、入力が次のような場合

[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