# Longest Increasing Path in a Matrix

Given an m x n integers matrix, return *the length of the longest increasing path in *matrix.

From each cell, you can either move in four directions: left, right, up, or down. You **may not** move **diagonally** or move **outside the boundary** (i.e., wrap-around is not allowed).

```
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
row = len(matrix); col = len(matrix[0])
res = 0
memo = {}
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
def helper(i, j):
if (i,j) in memo: return memo[(i,j)]
path = 1
for move in directions:
r = i + move[0]
c = j + move[1]
if (0<=r<row and 0<=c<col and
matrix[r][c] != '#' and matrix[r][c] > matrix[i][j]):
tmp = matrix[i][j]
matrix[i][j] = '#'
path = max(path, helper(r, c) + 1)
matrix[i][j] = tmp
memo[(i,j)] = path
return memo[(i,j)]
for i in range(row):
for j in range(col):
res = max(res, helper(i, j))
return res
# Time: O(N^3)
# Space: O(N^2)
```

## Related Problems

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in **any order**.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.