**Solution**

**Longest Increasing Path in a Matrix** https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

**Brute Force**

- Brute force will be to run DFS at each node and choose the next neighbor based on the condition that its value is more than the current one. You will need a visited matrix here to prevent recomputation.

**Memoization**

- You can use a memoization cache. The beauty is that once you do that, you no longer even need a visited matrix.

```
from collections import defaultdict
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if matrix == []:
return 0
M, N, result = len(matrix), len(matrix[0]), 0
cache = defaultdict(lambda: defaultdict(int))
for i in range(M):
for j in range(N):
result = max(result, self.dfs(i,j, matrix, cache))
return result
def dfs(self, i, j, matrix, cache):
if i in cache and j in cache[i]:
return cache[i][j]
candidates, cache[i][j] = ((i+1, j), (i-1, j), (i, j+1), (i, j-1)), 1
for a,b in candidates:
if 0 <= a < len(matrix) and 0 <= b < len(matrix[0]) and matrix[i][j] < matrix[a][b]:
cache[i][j] = max(cache[i][j], 1+self.dfs(a,b,matrix,cache))
return cache[i][j]
```