Python, easy understand, memoized DP


  • 0
    A
    class Solution(object):
        def longestIncreasingPath(self, m):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            direct = [[-1, 0], [1, 0],[0, -1],[0, 1]]
            
            def dfs(memo, m, row, col, pre_v):
                if not (0 <= row < len(m) and 0 <= col < len(m[0])):
                    return 0
                else:
                    current_v = m[row][col]
                    if pre_v >= current_v:
                        return 0
                    else:
                        if memo[row][col] == -1:
                            memo[row][col] = 0
                            for y, x in direct:
                                memo[row][col] = max(memo[row][col], dfs(memo, m, row+y, col+x, current_v)+1)
                        return memo[row][col]
                    
            memo = [[-1] * len(m[0]) for _ in range(len(m))]
            ret = 0
            for row in range(len(m)):
                for col in range(len(m[0])):
                    ret = max(ret, dfs(memo, m, row, col, -float("INF")))
            return ret

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.