12 lines python solution DP O(MN)


  • 0
    B

    Our core idea is for each spot if we end at this spot, longest path equal to the node that around it with the longest path and smaller value. so we sort all node with value. then use DP to see how long we can reach

    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            if (not matrix) or (not matrix[0]): return 0
            dic,ve,re,m,n = {},[],1,len(matrix),len(matrix[0])
            for i in xrange(len(matrix)):
                for j in xrange(len(matrix[0])):
                   ve.append((matrix[i][j],i,j))
                   dic[(i,j)] = 1
            for val,x,y in sorted(ve):
                for i,j in [(x+i,y+j) for i,j in [(1,0),(0,1),(-1,0),(0,-1)]]:
                    if i>=0 and i<m  and j>=0 and j<n and matrix[i][j] > val :
                        dic[(i,j)] = max(dic[(i,j)],dic[(x,y)]+1)
                        re = max(re,dic[(i,j)])
            return re
            
    

Log in to reply
 

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