329. Longest Increasing Path in a Matrix

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Python

Backtracking (Timelimit Exceed)

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        cach = dict()
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        ans = 0

        def backtrack(path, pre, row, col):
            nonlocal ans

            cur = matrix[row][col]
            if cur <= pre:
                return

            path.add((row, col))
            # print(row, col, path)
            ans = max(ans, len(path))
            for rx, cx in directions:
                nr, nc = row+rx, col+cx
                if 0 <= nr < m and 0 <= nc < n:
                    backtrack(path, cur, nr, nc)
            path.remove((row, col))

        for row in range(m):
            for col in range(n):
                backtrack(set([(row, col)]), -1, row, col)

        return ans

Backtracking with cache

from functools import cache

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        ans = 0

        @cache
        def backtracking(row, col):
            nonlocal matrix

            cur = matrix[row][col]
            matrix[row][col] = -1

            reachable = 0
            for rx, cx in directions:
                nr, nc = row+rx, col+cx
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > cur:
                    reachable = max(
                        reachable,
                        backtracking(nr, nc)
                    )

            matrix[row][col] = cur
            return reachable + 1

        reachable = 0
        for row in range(m):
            for col in range(n):
                reached = backtracking(row, col)
                reachable = max(reachable, reached)

        return reachable