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

• ``````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.

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