题意整理:

题目给出一个元素为非负整数的矩阵，要求计算出矩阵中任意起点开始，每次只能向上下左右移动且不允许重复访问一个格子时，并且要求只能够向数值更大的格子移动时，能够得到的最大长度

方法一：深度优先搜索 + 记忆化

核心思想：

可以利用深度优先搜索解决本题。对于两个单元格，值较小的格子可以有一条路径前往相邻的值较大的格子，所以可以对每个单元格进行深度优先搜索，一直往下到无法前进，得到一条路径长度。每次到达一个单元格时考虑四个方向的转移。对每个单元格分别进行深度优先搜索之后，即可得到矩阵中的最长递增路径的长度。
以上分析已经可以正确的找到最长递增路径，但无法通过全部测试，原因在于简单的深度优先搜索的时间复杂度是指数级，会超出时间限制，需要加以优化。普通的深度优先搜索的时间复杂度过高的原因是进行了大量的重复计算，同一个单元格会被访问多次，而每次访问都进行了一次计算。对于同一个单元格，其对应的最长递增路径的长度是不变的，因为只能怪往数值更大的方向走。所以可以使用记忆化的方法进行优化。用一个矩阵记录已经计算过的单元格的结果。

核心代码：

class Solution {
public:
    int turn[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//四个方向移动
    int m, n;

    int dfs(vector<vector<int>>& matrix, int x, int y, vector<vector<int>>& rem) {
        if (rem[x][y] != 0) {//已经搜索过的直接返回
            return rem[x][y];
        }
        ++rem[x][y];
        for (int i = 0; i < 4; ++i) {
            //对四个方向进行深搜
            int newx = x + turn[i][0], newy = y + turn[i][1];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && matrix[newx][newy] > matrix[x][y]) {
                rem[x][y] = max(rem[x][y], dfs(matrix, newx, newy, rem) + 1);
            }
        }
        return rem[x][y];
    }

    int solve(vector<vector<int> >& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        m = matrix.size();
        n = matrix[0].size();
        vector<vector<int>> rem(m, vector<int>(n));//记录搜索结果，避免重复计算
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans = max(ans, dfs(matrix, i, j, rem));//逐个搜索
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：，其中 分别为矩阵的行数和列数。深度优先搜索的时间复杂度是 ，其中 是节点数， 是边数。在矩阵中，节点数即为 ，边数为
空间复杂度：，其中 分别为矩阵的行数和列数。使用的记忆化数组大小为 , 递归调用的深度不会超过 , 故空间复杂度为 。

方法二：拓扑排序 + 广度优先搜索

核心思想：

可以发现，对矩阵中的一个单元格，其最长递增路径的结果只和相邻单元格的结果有关。
对于两个矩阵中的相邻单元格 ， ，如果满足 则可以从 转移到 ，故 ,其中 与在矩阵中相邻且。
且对于出度为 的单元格有.从出度为0的单元格开始转移，最多能够转移的此时即为矩阵的最长递增路径。
为了得到转移路线，可以先对单元格拓扑排序求解。之后从所有出度为 的单元格开始广度优先搜索，每轮搜索都遍历当前层的所有单元格，更新其余单元格的出度，并将出度变为 的单元格加入下一层搜索。当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度。

核心代码：

class Solution {
public:
    int turn[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//四个方向移动
    int m, n;

    int solve(vector<vector<int> >& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        m = matrix.size();
        n = matrix[0].size();
        vector<vector<int>> f(m, vector<int>(n));//记录出度
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                for(int k = 0; k < 4; ++k) {
                    //计算出度
                    int newx = i + turn[k][0], newy = j + turn[k][1];
                    if(newx >= 0 && newx < m && newy >= 0 && newy < n && matrix[newx][newy] > matrix[i][j]) {
                        f[i][j] += 1;
                    }
                }
            }
        }
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (f[i][j] == 0) {//将出度为0的加入队列，作为广度优先遍历的起始点
                    q.push({i, j});
                }
            }
        }
        int ans = 0;
        while (!q.empty()) {
            ++ans;
            int len = q.size();
            //将整层的节点进行计算
            for (int i = 0; i < len; ++i) {
                int x = q.front().first, y = q.front().second;
                q.pop();
                for (int k = 0; k < 4; ++k) {
                    int newx = x + turn[k][0], newy = y + turn[k][1];
                    if (newx >= 0 && newx < m && newy >= 0 && newy < n && matrix[newx][newy] < matrix[x][y]) {
                        --f[newx][newy];
                        if (f[newx][newy] == 0) {
                            //出度为0，说明能够转移到它的节点都计算完毕，开始对其进行计算
                            q.push({newx, newy});
                        }
                    }
                }
            }
        }
        return ans;//广搜轮数即为答案
    }
};

复杂度分析：

时间复杂度：,其中 分别为矩阵的行数和列数。拓扑排序的时间复杂度是 ，其中 是节点数， 是边数。在矩阵中，节点数即为 ，边数为
空间复杂度：，其中 分别为矩阵的行数和列数。使用的队列空间不会超过，以及使用一个大小为 的数组记录出度