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

https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/

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

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

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

解法一：记忆化搜索优化DFS

很容易想到用DFS挨个查找以每个单元格为起点的最长递增路径，只是这么做时间复杂度必然爆炸，如何优化呢？

我们可以用动态规划的思想：建立数组dp[i][j]，用以保存单元格[i][j]作为起点的最长路径。在DFS过程中动态维护dp数组，每求得一个单元格的最长递增路径，就将其保存在dp中，然后再继续DFS进程。
同时，我们还需要一个辅助数组visited[i][j]，用以记录在整个DFS进程中，单元格[i][j]是否已经到访过，如果结果是肯定的，则不再重复到访。

DFS的主体逻辑如下：

到访一个单元格[currx][curry]，初来乍到，记它的最长递增路径（即本身到本身）dp[currx][curry]为1；
向4个方向查探[currx][curry]的下一个单元格[nextx][nexty]，若查探到的[nextx][nexty]对于matrix已经越界，或者对于[currx][curry]并不递增，则直接跳过这个位置；
单元格[nextx][nexty]相对于[currx][curry]是递增的，这说明，[currx][curry]作为起点的最长递增路径一定不小于[nextx][nexyx]作为起点的最长递增路径+1，即dp[currx][curry]=max(dp[currx][curry],dp[nextx][nexty]+1)，我们需要按照这个式子，对dp[currx][curry]进行维护；
那么，单元格[nextx][nexyx]作为起点的最长递增路径是否已知呢？这就要用到visited数组了。询问visited数组后，如果发现单元格[nextx][nexty]已经拜访过，那么它是在DFS中已经求过最长递增路径的，直接在dp数组中读取dp[nextx][nexty]就可以；如果没有拜访过，则还需要调用DFS对单元格[nextx][nexty]进行拜访；
4个方向查探完成后，对当前单元格最长递增路径的的维护已经完成，在visited数组中标记[currx][curry]已经拜访过，并更新目前为止碰到过的最长路径maxPath。

最后，我们就以对每个单元格只拜访一遍的方式，求得了要返回的maxPath。
时间复杂度：O(mn)
空间复杂度：O(mn)

代码

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        xlen=matrix.size();
        ylen=matrix[0].size();
        this->matrix=matrix;
        maxPath=0;
        dp.resize(xlen);    //动规数组
        visited.resize(xlen);   //记录已经到访过的单元格
        for(int i=0; i<xlen; i++)   //初始化
        {
            for(int j=0; j<ylen; j++)   
            {
                dp[i].push_back(0);
                visited[i].push_back(false);
            }
        }
        //依次遍历每个未到访过的单元格，利用dfs搜索其最长递增路径，并记录在dp数组中
        for(int i=0; i<xlen; i++)   
        {
            for(int j=0; j<ylen; j++)
            {
                if(visited[i][j]==true)    continue;   //已到访则跳过
                dfs(i,j);
            }
        }
        return maxPath;
    }
    void dfs(int currx,int curry)    //深度优先搜索
    {
        dp[currx][curry]=1; //该单元格的最长递增路径的长度至少为1
        for(int k=0; k<4; k++)  //向四个方向查探
        {
            int nextx=currx+mvx[k],nexty=curry+mvy[k];
            if(nextx<0||nextx>=xlen||nexty<0||nexty>=ylen)  continue;   //越界，跳过
            if(matrix[nextx][nexty]<=matrix[currx][curry])  continue;   //不增，跳过
            //next所指单元格相对curr递增:
            if(visited[nextx][nexty]==true) //next已到访，直接利用dp_next维护dp_curr
            {
                dp[currx][curry]=max(dp[currx][curry],dp[nextx][nexty]+1);
            }else{  //next未到访，dfs访问next后再利用dp_next维护dp_curr
                dfs(nextx,nexty);
                dp[currx][curry]=max(dp[currx][curry],dp[nextx][nexty]+1);
            }
        }
        //四个方向查探完毕后，对dp_curr的维护已经完成，标记curr已到访
        visited[currx][curry]=true;
        maxPath=max(maxPath,dp[currx][curry]);  //更新最长路径
    }


private:
    int mvx[4]={1,0,-1,0};
    int mvy[4]={0,1,0,-1};
    vector<vector<int>> matrix;
    vector<vector<int>> dp; //动态维护每个单元格的最长递增路径
    vector<vector<bool>> visited;
    int xlen,ylen;
    int maxPath;
};

解法二：基于BFS的拓扑排序

先遍历一遍maxtrix，用数组outdegree[i][j]记录每个单元格的“出度”——也就是单元格[i][j]周围4个相邻单元格中，有几个单元格的值大于单元格[i][j]。
若一个单元格的出度为0，则代表它在某条递增路径的末端。出度为0的单元格进入队列q，准备BFS。也就是说，队列q保存了所有递增路径的最后一个单元格。
在BFS中，我们每次对所有递增路径的最后一个单元格进行一套移除操作。移除单元格[i][j]后，在周围4个单元格中，小于[i][j]的单元格出度减1，把新的出度为0的单元格加入队列。在完成一套移除操作后，队列中就存储了所有递增路径的倒数第二个单元格，也就是新的最后一个单元格。
每完成一套操作，计数maxPath加1，直至队列为空时，所有递增路径都已经删空，此时的maxPath为最耐移除的递增路径被移除的次数，也就是最长递增路径的长度。

所有单元格都只被移除了一次。
时间复杂度：O(mn)
空间复杂度：O(mn)

代码

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int xlen=matrix.size(),ylen=matrix[0].size();
        int mvx[4]={1,0,-1,0};
        int mvy[4]={0,1,0,-1};
        vector<vector<int>> outdegree(xlen,vector<int>(ylen,0));
        queue<pair<int,int>> q;
        //拓扑排序的准备工作：记录每个单元格的出度，出度为0的单元格入队
        for(int i=0; i<xlen; i++)
        {
            for(int j=0; j<ylen; j++)
            {
                int curr=matrix[i][j];
                for(int k=0; k<4; k++)
                {
                    if(i+mvx[k]<0||i+mvx[k]>=xlen||j+mvy[k]<0||j+mvy[k]>=ylen)
                        continue;
                    if(curr<matrix[i+mvx[k]][j+mvy[k]])
                        outdegree[i][j]++;
                }
                if(outdegree[i][j]==0)  q.push({i,j});
            }
        }
        int maxPath=0;
        //广度优先搜索：出度为0的单元格在最长递增路径末端，处理所有出度为0的单元格，并更新其四个方向的单元格的出度，并将新的出度为0的单元格入队
        while(!q.empty())
        {
            int sz=q.size();
            for(int i=0; i<sz; i++)
            {
                int x=q.front().first,y=q.front().second;   //当前出度为0的单元格
                q.pop();
                for(int k=0; k<4; k++)  //更新四个方向单元格的出度
                {
                    if(x+mvx[k]<0||x+mvx[k]>=xlen||y+mvy[k]<0||y+mvy[k]>=ylen)
                        continue;
                    if(matrix[x+mvx[k]][y+mvy[k]]<matrix[x][y])
                    {
                        outdegree[x+mvx[k]][y+mvy[k]]--;
                        if(outdegree[x+mvx[k]][y+mvy[k]]==0)  //出度减至0的单元格入队
                            q.push({x+mvx[k],y+mvy[k]});
                    }
                }
            }
            maxPath++;  //处理完一层队列，最长递增路径长度加1
        }
        return maxPath;
    }
};