[LeetCode] 329. Longest Increasing Path in a Matrix

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

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        diff = ((0,1), (0,-1), (1,0), (-1,0))
        
        @cache
        def helper(y, x):
            """
            Longest increasing path starts from matrix[y][x]
            """
            result = 1
            for dx, dy in diff:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < COLUMN and 0 <= ny < ROW and matrix[y][x] < matrix[ny][nx]:
                    # increasing sequence can only be built with one direction
                    # no need to mark the visited positions
                    result = max(result, 1 + helper(ny, nx))
            
            return result
        
        result = 1
        for y in range(ROW):
            for x in range(COLUMN):
                result = max(result, helper(y,x))
        return result

Edited on 04/10/2021. Use @cache annotation.