โปรแกรมหาจำนวนเหรียญสูงสุดที่เรารวบรวมได้ใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติที่แต่ละเซลล์เก็บเหรียญไว้ หากเราเริ่มต้นจาก [0,0] และสามารถเคลื่อนที่ไปทางขวาหรือลงได้เท่านั้น เราต้องหาจำนวนเหรียญสูงสุดที่เรารวบรวมได้จากมุมขวาล่าง

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 14 ในขณะที่เราใช้เส้นทาง:[1, 4, 2, 2, 5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• สำหรับ r ในช่วง 1 ถึงจำนวนแถวของ A ทำ

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

• สำหรับ c ในช่วง 1 ถึงจำนวนคอลัมน์ของ A ทำ

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

  • สำหรับ r ในช่วง 1 ถึงขนาด A ทำ

  • สำหรับ c ในช่วง 1 ถึงขนาด A[0] ให้ทำ

  • A[r, c] =A[r, c] + สูงสุดของ (A[r-1, c] และ A[r, c-1]

• ส่งคืนค่าที่มุมล่างขวาของ A

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น−

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

14