เส้นทางเพิ่มขึ้นที่ยาวที่สุดในเมทริกซ์ (Longest Increasing Path) ใน Python

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

เช่น หากอินพุทเป็นดังนี้

ผลลัพธ์จะเป็น 4 เนื่องจากเส้นทางเพิ่มขึ้นที่ยาวที่สุดคือ [3, 4, 5, 6] (หมายเหตุ: ตัวอย่างในต้นฉบับอาจมีความคลาดเคลื่อนในค่าที่แสดง)

วิธีแก้ปัญหา (ใช้ Dynamic Programming + DFS):

• กำหนดฟังก์ชัน solve() รับ i, j, matrix

• ถ้า dp[i][j] ไม่เป็นศูนย์ คืนค่า dp[i][j]

• dp[i][j] := 1

• temp := 0

• วนลูป r จาก i-1 ถึง i+1, และ c จาก j-1 ถึง j+1

• ข้ามถ้า (r,c) คือ (i,j) หรือเป็นแนวทแยง

• ถ้า (r,c) อยู่ในขอบเขต และ matrix[r][c] > matrix[i][j] ให้ temp = max(temp, solve(r, c, matrix))

• dp[i][j] += temp

• คืนค่า dp[i][j]

• จากเมธอดหลัก: สร้าง dp ขนาดเท่า matrix เติม 0, วนลูปทุกเซลล์ เรียก solve(), เก็บค่าสูงสุด

ตัวอย่างการใช้งาน

class Solution(object):
    def solve(self, i, j, matrix):
        if self.dp[i][j]:
            return self.dp[i][j]
        self.dp[i][j] = 1
        temp = 0
        for r in range(i-1, i+2):
            for c in range(j-1, j+2):
                if r == i and c == j or (abs(r-i) == 1 and abs(c-j) == 1):
                    continue
                if c >= 0 and r >= 0 and r < len(matrix) and c < len(matrix[0]) and matrix[r][c] > matrix[i][j]:
                    temp = max(temp, self.solve(r, c, matrix))
        self.dp[i][j] += temp
        return self.dp[i][j]
    
    def longestIncreasingPath(self, matrix):
        if not matrix:
            return 0
        self.dp = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        self.ans = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dp[i][j] == 0:
                    self.solve(i, j, matrix)
                self.ans = max(self.ans, self.dp[i][j])
        return self.ans

ob = Solution()
print(ob.longestIncreasingPath([[9, 9, 4], [6, 6, 8], [2, 1, 1]]))

อินพุท

[[9, 9, 4], [6, 6, 8], [2, 1, 1]]

เอาต์พุท

4