Top Down DP Solution in python


  • 0
    I
        def _within_bounds(self, row, col, rows, cols):
            return 0 <= row < rows and 0 <= col < cols
        
        def _calc_lip(self, matrix, row, col, LIP):
            if LIP[row][col] != 0:
                return LIP[row][col]
                
            LIP[row][col] = 1
            rows = len(matrix)
            cols = len(matrix[0])
            
            for row_disp, col_disp in [(0,1),(0,-1),(1,0),(-1,0)]:
                dest_row = row + row_disp
                dest_col = col + col_disp
                if not self._within_bounds(dest_row, dest_col, rows, cols):
                    continue
                
                if matrix[dest_row][dest_col] < matrix[row][col]:
                    LIP[row][col] = max(LIP[row][col], 1 + self._calc_lip(matrix, dest_row, dest_col, LIP))
                    
            return LIP[row][col]
        
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            if not matrix:
                return 0
                
            rows = len(matrix)
            cols = len(matrix[0])
            max_lip = 1
            LIP = [[0 for j in xrange(cols)] for i in xrange(rows)]
            
            for row in xrange(rows):
                for col in xrange(cols):
                    max_lip = max(max_lip, self._calc_lip(matrix, row, col, LIP))
                    
            return max_lip

Log in to reply
 

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