Python bottom-up and top-down DP solutions with detailed explanations


  • 1
    class Solution(object):
    
        def _longestIncreasingPath(self, matrix):
        
            # This is the top-down DP solution. We can see this
            # problem as a graph problem, in which we have as nodes
            # the matrix's elements. There is an edge between node i
            # and node j iff j > i, i and j are in the matrix, and
            # j is in the neighborhood of i. 
            # So a DFS/BFS from every
            # node will solve the problem.
        
        
            def dfs(z, matrix, memo):
                if z in memo:
                    return memo[z]
                g = 0
                for n in (z-1, z+1, z+1j, z-1j):
                    if n in matrix and matrix[z] > matrix[n]:
                        g = max(g, dfs(n, matrix, memo))
                memo[z] = 1 + g
                return memo[z]
        
            d = {}
            for r, row in enumerate(matrix):
                for c, val in enumerate(row):
                    d[r + c*1j] = val
            
            matrix, res, memo = d, 0, {}
            for z in matrix:
                res = max(res, dfs(z, matrix, memo))
            return res
            
            
            
        def longestIncreasingPath(self, matrix):
            
            # This is a Bottom-up DP solution. Since we are not recursing, we
            # need to build the max length for each node in the matrix by starting
            # from the nodes that have no ingress edge. So we need to do a topsort.
            # to process the nodes in the correct way.
            
            # But in our case, we know that the nodes having minimum value will
            # not have ingress edges. Consider this matrix:
            
            # M = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
            # 
            #  The graph will be 
            # 1 ---X  8  X--- 4
            #         X
            #         |    
            # 1 ---X  6 ---X  9
            # |
            # |
            # X
            # 2 ----X 6 ---X  9
            
            # So the order of exploration in top sort is 1, 1, 2, 4, 6, 6, 8, 9, 9.
            # But this is just the matrix's elements sorted! This simplifies a lot
            # the implementation.
            
            
            d = {}
            for r, row in enumerate(matrix):
                for c, val in enumerate(row):
                    d[r + c*1j] = val
            matrix = d
            dp, res = {}, 0
            for z in sorted(matrix, key=matrix.get):
                g = 0
                for n in (z+1, z-1, z+1j, z-1j):
                    if n in matrix and matrix[z] > matrix[n]:
                        g = max(g, dp[n])
                dp[z] = 1 + g
                res = max(res, dp[z])
            return res
    
    # Runtime Top-down: 580ms
    # Runtime Bottom-up: 524ms
    

    Note how the matrix preprocessing and the use of complex numbers eases implementation. Kudos to the amazing @StefanPochmann for showing me this Python capability I was not aware of.


Log in to reply
 

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