> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/graph/329-longest-increasing-path-in-a-matrix.md).

# 329 Longest Increasing Path in a Matrix

## 329. [Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/)

## 1. Question

Given an integer matrix, find the length of the longest increasing path.

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

**Example 1:**

```
nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]
```

Return`4`\
The longest increasing path is`[1, 2, 6, 9]`.

**Example 2:**

```
nums = [
  [3,4],5],
  [3,2,6],
  [2,2,1]
]
```

Return`4`\
The longest increasing path is`[3, 4, 5, 6]`. Moving diagonally is not allowed.

## 2. Implementation

**(1) DFS + memoinzation**

```java
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n];
        int maxLen = 1;

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = getLengthOfIncreasingPath(i, j, matrix, cache, directions);
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }

    public int getLengthOfIncreasingPath(int row, int col, int[][] matrix, int[][] cache, int[][] directions) {
        if (cache[row][col] != 0) {
            return cache[row][col];
        }

        int curMaxLen = 1;

        for (int[] direction : directions) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (isValid(row, col, nextRow, nextCol, matrix)) {
                int len = 1 + getLengthOfIncreasingPath(nextRow, nextCol, matrix, cache, directions);
                curMaxLen = Math.max(curMaxLen, len);
            }
        }

        cache[row][col] = curMaxLen;
        return curMaxLen;
    }

    public boolean isValid(int curRow, int curCol, int nextRow, int nextCol, int[][] matrix) {
        return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[curRow][curCol] < matrix[nextRow][nextCol];
    }
}
```

## 3. Time & Space Complexity

**DFS + memoinzation:** 时间复杂度O(mn)，空间复杂度O(mn)