โปรแกรมหาจำนวนเหรียญที่เราสามารถเลือกจากเซลล์บนซ้ายไปล่างขวาและส่งคืนใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติที่มีค่าที่เป็นไปได้ 3 ค่า -

• 0 สำหรับเซลล์ว่าง

• 1 สำหรับเหรียญ

• -1 สำหรับกำแพง

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

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

แล้วผลลัพธ์จะเป็น 8

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

• n :=จำนวนแถวของเสื่อ m :=จำนวนคอลัมน์ของเสื่อ

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา i, j, k, l

• ถ้า i และ j ไม่อยู่ในช่วงของ mat หรือ mat[i, j] จะเท่ากับ -1 ดังนั้น

  • กลับ −inf

• ถ้า k และ l ไม่อยู่ในช่วงของ mat หรือ mat[k, l] เท่ากับ -1 ดังนั้น

  • กลับ −inf

• ถ้าฉัน, j, k และ l ทั้งหมดเป็น 0 แล้ว

  • เสื่อกลับ[0, 0]

• ดีที่สุด :=−inf

• สำหรับแต่ละคู่ (dx1, dy1) ใน [(-1, 0) ,(0, −1) ] ทำ

  • สำหรับแต่ละคู่ (dx2, dy2) ใน [(-1, 0) ,(0, −1) ] ทำ

    • ดีที่สุด :=สูงสุดของ best และ util(i + dy1, j + dx1, k + dy2, l + dx2)

• return mat[i, j] +(1 เมื่อ i ไม่เหมือนกับ k มิฉะนั้น 0) * mat[k, l] + ดีที่สุด

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ผลตอบแทนสูงสุดเป็น 0 และ util(n − 1, m − 1, n − 1, m − 1)

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

ตัวอย่าง

class Solution:
   def solve(self, mat):
      n, m = len(mat), len(mat[0])
      def util(i, j, k, l):
         if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1:
            return −1e9
         if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1:
            return −1e9
         if i == 0 and j == 0 and k == 0 and l == 0:
            return mat[0][0]
         best = −1e9
         for dx1, dy1 in [(−1, 0), (0, −1)]:
            for dx2, dy2 in [(−1, 0), (0, −1)]:
               best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
         return mat[i][j] + (i != k) * mat[k][l] + best
      return max(0, util(n − 1, m − 1, n − 1, m − 1))
ob = Solution()
matrix = [
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]
print(ob.solve(matrix))

อินพุต

[
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]

ผลลัพธ์

8