Chương trình tìm số lượng xu tối đa mà chúng tôi có thể thu thập bằng Python

Giả sử chúng ta có một ma trận 2D trong đó mỗi ô lưu trữ một số đồng tiền. Nếu chúng ta bắt đầu từ [0,0] và chỉ có thể di chuyển sang phải hoặc xuống dưới, chúng ta phải tìm số lượng xu tối đa mà chúng ta có thể thu thập ở góc dưới cùng bên phải.

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

thì đầu ra sẽ là 14, khi chúng ta đi theo đường dẫn:[1, 4, 2, 2, 5]

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

• đối với r trong phạm vi 1 đến số hàng của A, thực hiện

  • A [r, 0]:=A [r, 0] + A [r-1, 0]

• đối với c trong phạm vi 1 đến số cột của A, thực hiện

  • A [0, c]:=A [0, c] + A [0, c-1]

  • đối với r trong phạm vi từ 1 đến kích thước của A, thực hiện

  • đối với c trong phạm vi 1 đến kích thước của A [0], thực hiện

  • A [r, c] =A [r, c] + tối đa của (A [r-1, c] và A [r, c-1]

• giá trị trả về của góc dưới cùng bên phải của A

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

Đầu vào

matrix = [
   [1, 4, 2, 2],
   [6, 0, 0, 5]
]

Đầu ra

14