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

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

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：

输入：matrix = [[1]]
输出：1

深度优先搜索-递归

对于每一个位置，其上下左右四个方向中，比当前位置值大的值与当前值必然组成长度不小于2的段。
求得每个位置的最长递增路径长度后，遍历每个位置的值，即可求得答案。

当然，为了避免重复计算，使用数组记录已经求得的值。所以也叫记忆化深度优先搜索。

时间复杂度: O(mn),其中m和n为矩阵的长和宽。考虑矩阵为无向图，深度优先遍历的时间复杂度为O(V+E), 其中V、E分别为无向图的顶点和边。在矩阵中，O(V) = O(mn), O(E) = O(4mn) = O(mn)
空间复杂度：O(mn), 空间主要是缓存memo和递归调用的深度，memo为mn, 递归调用深度最坏是把所有矩阵元素连起来，长度不会超过m*n

class Solution {
    // 上下左右四个方向
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo, int row, int column, int rows, int columns) {
        if (memo[row][column] != 0) {
            return memo[row][column];
        }
        // 当前数字长度为1
        ++memo[row][column];
        for (int i = 0; i < 4; i++) {
            int newRow = row + dirs[i][0], newColumn = column + dirs[i][1];
            if (newRow>=0 && newRow < rows && newColumn>=0 && newColumn<columns && matrix[newRow][newColumn] > matrix[row][column]) {
                memo[row][column] = max(memo[row][column], dfs(matrix, memo, newRow, newColumn, rows, columns) + 1);
            }
        }
        return memo[row][column];
    }

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0) return 0;
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<int>> memo(rows, vector<int>(columns, 0));
        int ans = 0;
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                ans = max(ans, dfs(matrix, memo, row, column, rows, columns));
            }
        }
        return ans;
    }
};

动态规划

如果是动态规划，则是先计算值较大节点的路径长度，然后递推

可以考虑使用优先级队列对矩阵中元素进行排序，然后从大到小计算以元素i,j结尾的最大序列的长度：dp[i][j]
记录整个过程中最大的dp[i][j]值即为答案

dp[i][j]表示以元素(i, j)为开始节点的最大路径长度

时间和空间复杂度依然是O(m*n)

class Solution {
    // 上下左右四个方向
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(columns, 0));
        // 使用优先级队列排序, 默认是大顶堆，优先队列里面每个元素是元组
        priority_queue<tuple<int, int, int>> q;
        // priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
        int count = 0;
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                q.push({matrix[row][column], row, column});
                // q.push(make_tuple(matrix[row][column], row, column));
            }
        }

        int ans = 0;
        // 依次弹出栈顶元素, 也就是最大的数，计算该节点的dp值后再计算更小的，这里面最大的dp值即为答案
        while (!q.empty()) {
            auto cell = q.top(); q.pop();
            int row = get<1>(cell), column = get<2>(cell);
            // 单独一个数也能成为长度为1的路径
            ++dp[row][column];
            for (int direction = 0; direction < 4; direction++) {
                int newRow = row + dirs[direction][0], newColumn = column + dirs[direction][1];
                if (newRow>=0 && newRow < rows && newColumn>=0 && newColumn<columns && matrix[newRow][newColumn] > matrix[row][column]) {
                    dp[row][column] = max(dp[row][column], dp[newRow][newColumn]+1);
                }
            }
            ans = max(ans, dp[row][column]);
        }
        return ans;
    }
};

广度优先搜索-队列-拓扑排序

将矩阵看作是一个有向图，计算每个单元格对应的出度，即有多少条边从该节点出发，也就是相邻的四个顶点有几个点比该点大。

边界条件是出度为0的点，若为路径，必为路径结尾。

基于出度的概念，可以使用拓扑排序求解，从所有出度为0的单元格开始广度优先搜索，每一轮都会遍历当前队列中的所有节点，然后更新周围的节点，
并将出度为0的节点加入下一层。这样，分别遍历出度为0，相邻且出度为1，相邻且出度为2…的节点，当遍历结束时，搜索的总层数即为答案。

时间复杂度：O(mn)
空间复杂度：O(mn)

class Solution {
    // 上下左右四个方向
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int rows = matrix.size(), columns = matrix[0].size();
        // 存储出度
        vector<vector<int>> outdegrees(rows, vector<int>(columns, 0));
        queue<pair<int, int>> q;
        // 先更新每个点的出度, 并将更新后出度仍为0的点加入队列
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                for (int direction = 0; direction < 4; direction++) {
                    int newRow = row + dirs[direction][0], newColumn = column + dirs[direction][1];
                    if (newRow>=0 && newRow < rows && newColumn>=0 && newColumn<columns && matrix[newRow][newColumn] > matrix[row][column]) {
                        ++outdegrees[row][column];
                    }
                }
                // cout << outdegrees[row][column] << " ";
                if (outdegrees[row][column] == 0) q.push({row, column});
            }
            // cout << endl;
        }

        // 开始分层遍历，并记录层数。
        int ans = 0;
        while (!q.empty()) {
            ++ans;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto cell = q.front(); q.pop();
                int row = cell.first, column = cell.second;
                for (int direction = 0; direction < 4; direction++) {
                    int newRow = row + dirs[direction][0], newColumn = column + dirs[direction][1];
                    if (newRow>=0 && newRow < rows && newColumn>=0 && newColumn<columns && matrix[newRow][newColumn] < matrix[row][column]) {
                        --outdegrees[newRow][newColumn];
                        if (outdegrees[newRow][newColumn] == 0) q.push({newRow, newColumn});
                    }
                }
            }
        }
        return ans;
    }
};

汇芳书院

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

深度优先搜索-递归

动态规划

广度优先搜索-队列-拓扑排序