Đường đi tăng dài nhất trong ma trận với Python

Cho một ma trận, tìm độ dài đường đi tăng dài nhất. Từ mỗi ô, có thể di chuyển 4 hướng: trái, phải, lên, xuống. Không được đi chéo hoặc ra ngoài biên.

Ví dụ: ma trận [[9,9,4],[6,6,8],[2,1,1]] → kết quả 4 (đường đi [3,4,5,6] - sửa: đường đi thực tế là 1→2→6→9 hoặc tương tự).

Giải thuật

• Đệ quy có nhớ (DP) với memoization
• Từ mỗi ô (i,j), thử 4 hướng, chỉ đi đến ô có giá trị lớn hơn
• Lưu kết quả trung gian trong mảng dp
• Trả về max của tất cả dp[i][j]

Ví dụ triển khai

class Solution:
    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]]))

Đầu vào

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

Đầu ra

4