Tìm số tiền xu tối đa có thể thu thập được trong Python

Giả sử chúng ta có một ma trận 2D trong đó các ô đại diện cho số lượng tiền xu. Có hai người bạn thu thập tiền xu, ban đầu họ được đặt ở góc trên bên trái và góc trên bên phải. Chúng tuân theo các quy tắc sau:

• Từ ô (i, j), người thu thập 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ả tiền xu có sẵn, làm cho ô đó trở nên trống.
• Người thu thập có thể chọn ở lại một ô, nhưng tiền xu trong bất kỳ ô nào chỉ có thể được thu thập một lần.

Chúng ta cần tìm số tiền xu tối đa có thể thu thập được.

Ví dụ, nếu đầu vào như sau:

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

Giải pháp

Để giải quyết bài toán này, chúng ta thực hiện 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 hàm dp(r, c1, c2):
  • Nếu r == R, trả về 0
  • ans := A[r][c1] + (1 nếu c1 != c2 else 0) * A[r][c2]
  • base := ans
  • Với mỗi nc1 trong [c1 - 1, c1, c1 + 1]:
    • Với mỗi nc2 trong [c2 - 1, c2, c2 + 1]:
      • Nếu 0 <= nc1 < C và 0 <= nc2 < C, thì ans := max(ans, base + dp(r + 1, nc1, nc2))
  • Trả về ans
• Trả về dp(0, 0, C - 1)

Ví dụ minh họa

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