โปรแกรมหาความยาวของเส้นทางเพิ่มขึ้นที่ยาวที่สุดในเมทริกซ์ใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติ เราต้องการหาความยาวของเส้นทางที่เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing path) สามารถเคลื่อนที่ได้ 4 ทิศทาง: บน, ล่าง, ซ้าย, ขวา (ไม่ได้ทแยง)

เช่น ถ้าข้อมูลนำเข้าคือ:

2 4 6
1 5 7
3 3 9

ขั้นตอนการแก้ปัญหา (DFS + Memoization)

• n := จำนวนแถว, m := จำนวนคอลัมน์
• moves := [[1,0], [-1,0], [0,1], [0,-1]]
• ฟังก์ชัน dp(y, x):
  • ถ้านอกขอบเขต คืน 0
  • currVal := matrix[y][x], res := 0
  • วนทุกทิศทาง d ใน moves:
    • คำนวณ newY, newX
    • ถ้าอยู่ในขอบเขตและ matrix[newY][newX] > currVal:
      • res := max(res, dp(newY, newX))
  • คืน res + 1
• จากเมธอดหลัก วนทุกเซลล์ หา max(dp(i, j))

ตัวอย่างโค้ด

class Solution:
    def solve(self, matrix):
        n, m = len(matrix), len(matrix[0])
        moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        def dp(y, x):
            if y < 0 or y >= n or x < 0 or x >= m:
                return 0
            currVal = matrix[y][x]
            res = 0
            for d in moves:
                dy, dx = d
                newY, newX = y + dy, x + dx
                if (0 <= newY < n and 0 <= newX < m and matrix[newY][newX] > currVal):
                    res = max(res, dp(newY, newX))
            return res + 1
        result = 0
        for i in range(n):
            for j in range(m):
                result = max(result, dp(i, j))
        return result

ob = Solution()
matrix = [
    [2, 4, 6],
    [1, 5, 7],
    [3, 3, 9]
]
print(ob.solve(matrix))

ข้อมูลนำเข้า

[ [2, 4, 6], [1, 5, 7], [3, 3, 9] ]

ผลลัพธ์

6