Pythonで収集できるコインの最大数を見つけるための問題

セルがその中のコインの数を表す2Dマトリックスがあるとします。コインを集める友達が2人いて、最初は左上隅と右上隅に配置されています。これらは次のルールに従います：

• セル（i、j）から、コインコレクターはセル（i + 1、j-1）、（i + 1、j）、または（i + 1、j + 1）に移動できます。

• セルに到達すると、利用可能なすべてのコインを収集してセルを空にします。

• コレクターは1つのセルに留まることを選択できますが、どのセルのコインも1回しか収集できません。

収集できるコインの最大数を見つける必要があります。

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

その場合、出力は17になります。

これを解決するには、次の手順に従います-

• A：=入力行列

• R：=Aの行数

• C：=Aの列数

• 関数dp（）を定義します。これにはr、c1、c2が必要です

  • rがRと同じ場合、

    • 0を返す

  • ans：=A [r、c1] +（c1がc2と等しくない場合、1、それ以外の場合は0）* A [r、c2]

  • ベース：=ans

  • [c1 − 1、c1、c1 + 1]の各nc1に対して、実行

    • [c2 − 1、c2、c2 + 1]の各nc2について、実行

      • 0 <=nc1

        • ans：=ansの最大値と（base + dp（r + 1、nc1、nc2））

  • 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