Chương trình tìm số tiền tối đa mà chúng ta có thể nhận được từ ma trận tiền xu biến mất trong Python

Giả sử chúng ta có một ma trận 2D trong đó mỗi ma trận ô [r, c] đại diện cho số đồng xu có trong ô đó. Khi chúng ta nhặt tiền từ ma trận [r, c], tất cả các đồng trên hàng (r - 1) và (r + 1) sẽ biến mất, cũng như các đồng ở hai ô ma trận [r, c + 1] và ma trận [r, c - 1]. Chúng tôi phải tìm số lượng xu tối đa mà chúng tôi có thể thu thập.

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

thì đầu ra sẽ là 26 vì chúng ta có thể chọn các ô có đồng tiền 8, 6, 9 và 3, vì vậy tổng số là 26.

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

• Xác định một hàm getmax (). Điều này sẽ mất khoảng thời gian
• pres_max:=0
• curr_max:=0
• res:=0
• đối với mỗi num trong arr, thực hiện
  • temp:=curr_max
  • curr_max:=num + pres_max
  • pres_max:=tối đa của nhiệt độ và pres_max
  • res:=tối đa res và curr_max
• trả lại res
• Từ phương thức chính, hãy làm như sau -
• nếu ma trận trống, thì
  • trả về 0
• m:=số hàng của ma trận
• n:=số cột của ma trận
• row_sum:=một mảng có kích thước m và điền bằng 0
• đối với tôi trong phạm vi từ 0 đến m - 1, thực hiện
  • row_sum [i]:=getmax (matrix [i])
• trả về getmax (row_sum)

Ví dụ

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

def getmax(arr):
   prev_max, curr_max = 0, 0
   res = 0
   for num in arr:
      temp = curr_max
      curr_max = num + prev_max
      prev_max = max(temp, prev_max)
      res = max(res, curr_max)
   return res

def solve(matrix):
   if not matrix:
      return 0
   m, n = len(matrix), len(matrix[0])
   row_sum = [0 for _ in range(m)]
   for i in range(m):
      row_sum[i] = getmax(matrix[i])
   return getmax(row_sum)

matrix = [
   [2, 8, 7, 6],
   [10, 10, 4, 2],
   [5, 9, 2, 3]
]
print(solve(matrix))

Đầu vào

[
[2, 8, 7, 6],
[10, 10, 4, 2],
[5, 9, 2, 3]
]

Đầu ra

26