สมมติว่า เรามีเมทริกซ์ 2 มิติ ซึ่งเซลล์แสดงจำนวนเหรียญในนั้น มีเพื่อนสองคนของเราที่จะเก็บเหรียญและพวกเขาจะถูกวางไว้ที่มุมบนซ้ายและที่มุมบนขวาที่จุดเริ่มต้น พวกเขาปฏิบัติตามกฎเหล่านี้:
-
จากเซลล์ (i, j) นักสะสมเหรียญสามารถย้ายไปยังเซลล์ (i + 1, j - 1), (i + 1, j) หรือ (i + 1, j + 1)
-
เมื่อไปถึงเซลล์ พวกเขาจะรวบรวมเหรียญทั้งหมดที่มีอยู่ทำให้เซลล์ว่าง
-
นักสะสมอาจเลือกที่จะอยู่ที่ห้องขังเดียว แต่เหรียญในช่องใด ๆ สามารถเก็บได้เพียงครั้งเดียว
เราต้องหาจำนวนเหรียญสูงสุดที่สามารถเก็บได้
ดังนั้นหากอินพุตเป็นแบบ
| 0 | 4 | 1 | 0 |
| 3 | 1 | 4 | 0 |
| 2 | 5 | 1 | 1 |
| 3 | 0 | 0 | 0 |
แล้วผลลัพธ์จะเป็น 17
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
A :=เมทริกซ์อินพุต
-
R :=จำนวนแถวของ A
-
C :=จำนวนคอลัมน์ของ A
-
กำหนดฟังก์ชัน dp() นี่จะใช้เวลา r, c1, c2
-
ถ้า r เหมือนกับ R แล้ว
-
คืนค่า 0
-
-
ans :=A[r, c1] +(ถ้า c1 ไม่เท่ากับ c2 แล้ว 1 อันอื่น 0) * A[r, c2]
-
ฐาน :=ans
-
สำหรับแต่ละ nc1 ใน [c1 − 1, c1, c1 + 1] ทำ
-
สำหรับแต่ละ nc2 ใน [c2 − 1, c2, c2 + 1] ทำ
-
ถ้า 0 <=nc1
-
ans :=สูงสุดของ ans และ (ฐาน + dp(r + 1, nc1, nc2))
-
-
-
-
กลับมาอีกครั้ง
-
-
กลับ dp(0, 0, C -1)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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] ]))
อินพุต
[ [0, 4, 1, 0], [3, 1, 4, 0], [2, 5, 1, 1], [3, 0, 0, 0] ]
ผลลัพธ์
17
