Chương trình tìm độ dài đường đi tăng dần dài nhất trong ma trận trong Python

Cho một ma trận 2D, tìm độ dài đường đi tăng dần nghiêm ngặt (strictly increasing) dài nhất. Chỉ được di chuyển lên, xuống, trái, phải (không chéo).

Ví dụ ma trận:

2 4 6
1 5 7
3 3 9

Giải thuật (DFS + Memoization / DP trên lưới)

• Khởi tạo mảng dp (hoặc dùng cache) để lưu độ dài đường đi dài nhất bắt đầu từ mỗi ô.
• Hàm dfs(y, x):
  • Nếu ngoài phạm vi, trả về 0.
  • Nếu đã tính, trả về giá trị cache.
  • Với 4 hướng di chuyển, nếu ô mới có giá trị > ô hiện tại: res = max(res, dfs(newY, newX)).
  • Lưu và trả về res + 1.
• Duyệt mọi ô, lấy max của dfs(i, j).

Mã nguồn Python

class Solution:
    def solve(self, matrix):
        n, m = len(matrix), len(matrix[0])
        moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        from functools import lru_cache
        @lru_cache(None)
        def dp(y, x):
            currVal = matrix[y][x]
            res = 0
            for dy, dx in moves:
                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))  # Output: 6

Đầu vào

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

Đầu ra

6