สมมติว่ามีเมทริกซ์ 2D ที่แต่ละเซลล์เก็บเหรียญ เริ่มจาก [0,0] เคลื่อนที่ได้เฉพาะขวาหรือลง หาจำนวนเหรียญสูงสุดที่เก็บได้เมื่อถึงมุมขวาล่าง
เช่น ถ้าอินพุตคือ [[1,4,2,2],[6,0,0,5]] ผลลัพธ์จะเป็น 14 ทางคือ [1,4,2,2,5]
ขั้นตอนการแก้ปัญหา
- for r ใน 1 ถึง จำนวนแถว A[r][0] += A[r-1][0]
- for c ใน 1 ถึง จำนวนคอลัมน์ A[0][c] += A[0][c-1]
- for r ใน 1 ถึง จำนวนแถว for c ใน 1 ถึง จำนวนคอลัมน์ A[r][c] += max(A[r-1][c], A[r][c-1])
- คืนค่า A[-1][-1]
ตัวอย่างโค้ด
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
