Vấn đề để tìm ra số lượng xu tối đa có thể được thu thập bằng Python

Giả sử, chúng ta có một ma trận 2D, trong đó các ô biểu thị số đồng xu trong đó. Có hai người bạn của chúng tôi để thu thập tiền xu, và chúng được đặt ở góc trên cùng bên trái và ở góc trên cùng bên phải khi bắt đầu. Họ tuân theo các quy tắc sau:

• Từ ô (i, j), người nhặt tiền có thể di chuyển đến ô (i ​​+ 1, j - 1), (i + 1, j) hoặc (i + 1, j + 1).

• Khi đến một ô, họ thu thập tất cả số xu có sẵn làm cho ô trống.

• Người thu thập có thể chọn ở lại một ô, nhưng tiền trong bất kỳ ô nào chỉ có thể được thu thập một lần.

Chúng tôi phải tìm số lượng xu tối đa có thể thu thập được.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 17.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• A:=ma trận đầu vào

• R:=số hàng của A

• C:=số cột của A

• Định nghĩa một hàm dp (). Điều này sẽ mất r, c1, c2

  • nếu r giống R thì

    • trả về 0

  • ans:=A [r, c1] + (nếu c1 không bằng c2 thì 1 khác 0) * A [r, c2]

  • base:=ans

  • đối với mỗi nc1 trong [c1 - 1, c1, c1 + 1], thực hiện

    • đối với mỗi nc2 trong [c2 - 1, c2, c2 + 1], thực hiện

      • nếu 0 <=nc1

        • ans:=tối đa ans và (base + dp (r + 1, nc1, nc2))

  • trả lại ans

• trả về dp (0, 0, C - 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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]
]))

Đầu vào

[
   [0, 4, 1, 0],
   [3, 1, 4, 0],
   [2, 5, 1, 1],
   [3, 0, 0, 0]
]

Đầu ra

17