คำอธิบายโจทย์
สมมติว่าเรามีเมทริกซ์ 2D ที่แต่ละเซลล์แสดงจำนวนเหรียญในเซลล์นั้น มีผู้เก็บเหรียญ 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
วิธีแก้ปัญหา
ใช้ Dynamic Programming แบบ Top-down พร้อม Memoization:
- A := เมทริกซ์อินพุต
- R := จำนวนแถวของ A, C := จำนวนคอลัมน์ของ A
- กำหนดฟังก์ชัน dp(r, c1, c2) ที่คืนค่าเหรียญสูงสุดจากแถว r จนจบ โดยผู้เก็บคนที่ 1 อยู่คอลัมน์ c1 และคนที่ 2 อยู่คอลัมน์ c2
- ถ้า r == R คืนค่า 0 (จบเมทริกซ์แล้ว)
- คำนวณเหรียญในแถวปัจจุบัน: ans = A[r][c1] + (c1 != c2) * A[r][c2]
- ลองทุกการเคลื่อนที่ที่เป็นไปได้ของทั้งสองคน (9 แบบ) และหาค่าสูงสุด
- คืนค่า dp(0, 0, C - 1)
โค้ด Python
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
from functools import lru_cache
@lru_cache(None)
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
