## Solution 1

Bottom-up DP, about 480 ms.

```
def longestIncreasingPath(self, matrix):
matrix = {i + j*1j: val
for i, row in enumerate(matrix)
for j, val in enumerate(row)}
length = {}
for z in sorted(matrix, key=matrix.get):
length[z] = 1 + max([length[Z]
for Z in z+1, z-1, z+1j, z-1j
if Z in matrix and matrix[z] > matrix[Z]]
or [0])
return max(length.values() or [0])
```

## Solution 2

Top-down DP, about 560 ms.

```
def longestIncreasingPath(self, matrix):
def length(z):
if z not in memo:
memo[z] = 1 + max([length(Z)
for Z in z+1, z-1, z+1j, z-1j
if Z in matrix and matrix[z] > matrix[Z]]
or [0])
return memo[z]
memo = {}
matrix = {i + j*1j: val
for i, row in enumerate(matrix)
for j, val in enumerate(row)}
return max(map(length, matrix) or [0])
```