solution.md

# 矩阵中的最长递增路径

<p>给定一个 <code>m x n</code> 整数矩阵 <code>matrix</code> ，找出其中 <strong>最长递增路径</strong> 的长度。</p>

<p>对于每个单元格，你可以往上，下，左，右四个方向移动。 你 <strong>不能</strong> 在 <strong>对角线</strong> 方向上移动或移动到 <strong>边界外</strong>（即不允许环绕）。</p>

<p> </p>

<p><strong>示例 1：</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/05/grid1.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>输入：</strong>matrix = [[9,9,4],[6,6,8],[2,1,1]]
<strong>输出：</strong>4 
<strong>解释：</strong>最长递增路径为 <code>[1, 2, 6, 9]</code>。</pre>

<p><strong>示例 2：</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/27/tmp-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>输入：</strong>matrix = [[3,4,5],[3,2,6],[2,2,1]]
<strong>输出：</strong>4 
<strong>解释：</strong>最长递增路径是 <code>[3, 4, 5, 6]</code>。注意不允许在对角线方向上移动。
</pre>

<p><strong>示例 3：</strong></p>

<pre>
<strong>输入：</strong>matrix = [[1]]
<strong>输出：</strong>1
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 <= m, n <= 200</code></li>
	<li><code>0 <= matrix[i][j] <= 2<sup>31</sup> - 1</code></li>
</ul>

<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp

```

## 答案

```cpp
class Solution
{
public:
    int m, n;
    vector<vector<int>> memo;
    int dfs(vector<vector<int>> &matrix, int x, int y)
    {
        if (memo[x][y] != -1)
            return memo[x][y];
        int ret = 1;
        if (x > 0 && matrix[x - 1][y] > matrix[x][y])
            ret = max(ret, 1 + dfs(matrix, x - 1, y - 1));
        if (x < m - 1 && matrix[x + 1][y] > matrix[x][y])
            ret = max(ret, 1 + dfs(matrix, x + 1, y + 1));
        if (y > 0 && matrix[x][y - 1] > matrix[x][y])
            ret = max(ret, 1 + dfs(matrix, x, y - 1));
        if (y < n - 1 && matrix[x][y + 1] > matrix[x][y])
            ret = max(ret, 1 + dfs(matrix, x, y + 1));
        memo[x][y] = ret;
        return ret;
    }
    int longestIncreasingPath(vector<vector<int>> &matrix)
    {
        m = matrix.size();
        if (m == 0)
            return 0;
        n = matrix[0].size();
        memo.resize(m);
        int ans = 1;
        for (int i = 0; i < m; ++i)
            memo[i].resize(n, -1);
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                int temp = dfs(matrix, i, j);
                ans = ans < temp ? temp : ans;
            }
        }
        return ans;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<vector<int>> state = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int longestIncreasingPath(vector<vector<int>> &matrix)
    {
        int n = matrix.size();
        if (n == 0)
            return 0;
        int m = matrix[0].size();

        vector<vector<int>> dp(n, vector<int>(m, 0));
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res = max(dfs(dp, matrix, i, j), res);
        return res;
    }

    int dfs(vector<vector<int>> &dp, vector<vector<int>> matrix, int i, int j)
    {
        if (dp[i][j] != 0)
            return dp[i][j];
        dp[i][j] = 1;
        for (vector<int> s : state)
        {
            int x = i + s[0];
            int y = j + s[1];
            if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size() && matrix[i][j] < matrix[x][y])
                dp[i][j] = max(dp[i][j], dfs(dp, matrix, x, y) + 1);
        }
        return dp[i][j];
    }
};
```

### B

```cpp
class Solution
{
public:
    vector<vector<int>> use;
    int dfs(int i, int j, vector<vector<int>> &matrix, int m, int n)
    {
        int len = 1, size, ans = 0;
        if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j])
        {
            if (use[i - 1][j] == 0)
                len = max(len, dfs(i - 1, j, matrix, m, n) + 1);
            else
                len = max(len, use[i - 1][j] + 1);
        }
        if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j])
        {
            if (use[i][j - 1] == 0)
                len = max(len, dfs(i, j - 1, matrix, m, n) + 1);
            else
                len = max(len, use[i][j - 1] + 1);
        }
        if (i + 1 < m && matrix[i + 1][j] > matrix[i][j])
        {
            if (use[i + 1][j] == 0)
                len = max(len, dfs(i + 1, j, matrix, m, n) + 1);
            else
                len = max(len, use[i + 1][j] + 1);
        }
        if (j + 1 < n && matrix[i][j + 1] > matrix[i][j])
        {
            if (use[i][j + 1] == 0)
                len = max(len, dfs(i, j + 1, matrix, m, n) + 1);
            else
                len = max(len, use[i][j + 1] + 1);
        }
        use[i][j] = len;
        return len;
    }
    int longestIncreasingPath(vector<vector<int>> &matrix)
    {
        if (matrix.empty() || matrix[0].empty())
            return 0;
        int m = matrix.size(), n = matrix[0].size();
        use = vector(m, vector<int>(n, 0));
        int i, j;
        int ans = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!use[i][j])
                    ans = max(ans, dfs(i, j, matrix, m, n));
            }
        }
        return ans;
    }
};
```

### C

```cpp
class Solution
{
public:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    int longestIncreasingPath(vector<vector<int>> &matrix)
    {
        if (matrix.size() == 0 || matrix[0].size() == 0)
        {
            return 0;
        }
        m = matrix.size();
        n = matrix[0].size();
        int res = 0;
        auto memo = vector<vector<int>>(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (memo[i][j])
                    res = max(res, memo[i][j]);
                else
                    res = max(res, dfs(i, j, matrix, memo));
            }
        }
        return res;
    }

    int dfs(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &memo)
    {
        int temp = 1;
        for (int k = 0; k < 4; ++k)
        {
            int x = i + dirs[k][0];
            int y = j + dirs[k][1];
            if ((x >= 0) && (x < m) && (y >= 0) && (y < n) && (matrix[i][j] < matrix[x][y]))
            {
                if (memo[x][y])
                    temp = max(temp, memo[x][y] + 1);
                else
                    temp = max(temp, dfs(x, y, matrix, memo) + 1);
            }
        }
        memo[i][j] = temp;
        return temp;
    }
};
```