329. 矩阵中的最长递增路径

回溯(超时)

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                backTrack(matrix, i, j, -1, 0);
        return ret;
    }
private:
    int ret = 0;
    void backTrack(vector<vector<int>>& matrix, int i, int j, int pre, int tmp)
    {
        if(i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size() || matrix[i][j] <= pre || matrix[i][j] == -1)
            return;
        pre = matrix[i][j];
        ++tmp;
        ret = max(tmp, ret);
        matrix[i][j] = -1;
        backTrack(matrix, i + 1, j, pre, tmp);
        backTrack(matrix, i - 1, j, pre, tmp);
        backTrack(matrix, i, j + 1, pre, tmp);
        backTrack(matrix, i, j - 1, pre, tmp);
        matrix[i][j] = pre;
    }
};

优化，记忆化dfs

因为前面走过来的路必然是小于当前的数字的，而接下来可以走的路必然是大于当前数字的，因此不用担心会走回头路。

而对于记忆化来说，不用担心这个记忆化的结果是从那边走来的，只需要知道获取这个记忆化数据的这一格必然大于记忆化的这一格，所以不可能是之前走过的路

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        memo.resize(m, vector<int>(n));
        int ret = 0;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                ret = max(ret, dfs(matrix, i, j, m, n));
        return ret;
    }
private:
    vector<vector<int>> memo;
    int dir[4][2]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int dfs(vector<vector<int>>& matrix, int i, int j, int m, int n)
    {
        if(memo[i][j])
            return memo[i][j];
        ++memo[i][j];
        for(int k = 0; k < 4; ++k)
        {
            int nextI = i + dir[k][0], nextJ = j + dir[k][1];
            if(nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && matrix[nextI][nextJ] > matrix[i][j])
                memo[i][j] = max(memo[i][j], dfs(matrix, nextI, nextJ, m, n) + 1);
        }
        return memo[i][j];
    }
};

dp，拓扑排序

从出度为0的点开始bfs，出度为0表示是矩阵中最大的点。然后往前bfs则表示往前一步走，当不能继续dfs时候就表示走到头了，具体看题解-方法二

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int dir[4][2]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        vector<vector<int>> outDegree(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 newI = i + dir[k][0], newJ = j + dir[k][1];
                    if(newI >= 0 && newJ >= 0 && newI < m && newJ < n && matrix[newI][newJ] > matrix[i][j])
                        ++outDegree[i][j];
                }
            }
        }
        queue<pair<int, int>> q;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(outDegree[i][j] == 0)
                    q.emplace(i, j);
        int ret = 0;
        while(!q.empty())
        {
            ++ret;
            for(int k = 0, sz = q.size(); k < sz; ++k)
            {
                auto [i, j] = q.front();
                q.pop();
                for(int l = 0; l < 4; ++l)
                {
                    int newI = i + dir[l][0], newJ = j + dir[l][1];
                    if(newI >= 0 && newJ >= 0 && newI < m && newJ < n && matrix[newI][newJ] < matrix[i][j])
                    {
                        if(--outDegree[newI][newJ] == 0)
                            q.emplace(newI, newJ);
                    }
                }
            }
        }
        return ret;
    }
};

题解中思考题的回答

「方法一」中使用了记忆化存储和深度优先搜索，这里的深度优先搜索可以替换成广度优先搜索吗？

不能，因为需要记录的是最长路径，而广度优先搜索只能记录一个层次的值
「方法二」中基于拓扑排序对排序后的有向无环图做了层次遍历，如果没有拓扑排序直接进行广度优先搜索会发生什么？

拓扑排序决定了dp的顺序，dp上一步决定下一步的值
「方法二」中如果不使用拓扑排序，而是直接按照矩阵中元素的值从大到小进行排序，并依此顺序进行状态转移，那么可以得到正确的答案吗？如果是从小到大进行排序呢？

可以，但慢，时间复杂度O(MNlog(MN))