12 lines python solution DP O(MN)

  • 0

    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])):
                   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.