The main idea is using DFS to search the longest increasing path from each point, and then cache the result for other paths passing it to use it.

```
class Solution(object):
def search(self, i, j, val, m, n, matrix, r):
if r[i][j] is not None:
return r[i][j]
length = 0
for x, y in ((0, -1), (-1, 0), (0, 1), (1, 0)):
ii, jj = i + x, j + y
if 0 <= ii < m and 0 <= jj < n and matrix[ii][jj] > val:
v = matrix[ii][jj]
matrix[ii][jj] = float('-inf')
length = max(self.search(ii, jj, v, m, n, matrix, r), length)
matrix[ii][jj] = v
r[i][j] = length + 1
return r[i][j]
def longestIncreasingPath(self, matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
r = [[None] * n for _ in xrange(m)]
return max(
self.search(i, j, val, m, n, matrix, r)
for i, row in enumerate(matrix)
for j, val in enumerate(row)
)
```