Wrong DP Python for reason


  • 0
    W
    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            n=len(matrix)
            if n==0:
                return 0
            m=len(matrix[0])
            if m==0:
                return 0
            re=[[1 for i in range(m)] for j in range(n)]
            max_len,old_max=1,0
            while max_len>old_max: 
                old_max=max_len
                for i in range(n):
                    for j in range(m):
                        if i-1>=0 and matrix[i][j]>matrix[i-1][j]:
                            re[i][j]=max(re[i][j],re[i-1][j]+1)
                        if i+1<=n-1 and matrix[i][j]>matrix[i+1][j]:
                            re[i][j]=max(re[i][j],re[i+1][j]+1)
                        if j-1>=0 and matrix[i][j]>matrix[i][j-1]:
                            re[i][j]=max(re[i][j],re[i][j-1]+1)
                        if j+1<=m-1 and matrix[i][j]>matrix[i][j+1]:
                            re[i][j]=max(re[i][j],re[i][j+1]+1)
                for i in range(n-1,-1,-1):
                    for j in range(m-1,-1,-1):
                        if i-1>=0 and matrix[i][j]>matrix[i-1][j]:
                            re[i][j]=max(re[i][j],re[i-1][j]+1)
                        if i+1<=n-1 and matrix[i][j]>matrix[i+1][j]:
                            re[i][j]=max(re[i][j],re[i+1][j]+1)
                        if j-1>=0 and matrix[i][j]>matrix[i][j-1]:
                            re[i][j]=max(re[i][j],re[i][j-1]+1)
                        if j+1<=m-1 and matrix[i][j]>matrix[i][j+1]:
                            re[i][j]=max(re[i][j],re[i][j+1]+1)
                    
                for i in range(n):
                    for j in range(m):
                        max_len=max(max_len,re[i][j])
           return max_len

Log in to reply
 

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