矩阵中的最长递增路径

﹏ヽ暗。殇╰゛Y 2024-03-31 10:29 142阅读 0赞

力扣题目

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

题目描述：

![56c6547292da4f38bfb81f161ec24c9e.png][]

解题思路：

看到这题，往上，下，左，右四个方向移动单元格，我的第一反应是运用深度优先搜索，但是单单使用到深度优先搜索的结果会超出时间限制，时间复杂度过高，进行了大量的重复运算，所以这道题还需要运用动态规划来进行优化，存储以前面单元格为起点的最长递增路径的长度，减少重复的计算。

先设置数组dp\[i\]\[j\]表示以单元格（i，j）为起点的最长递增路径的长度，遍历每个单元格，然后对于每个单元格，可以往上，下，左，右四个方向移动，通过设置数组来实现单元格上下左右移动时i和j的变化，我们可以对每个单元格进行深度优先搜索，当相邻的单元格b大于当前单元格时a，我们可以移动到这个相邻的单元格b。继续进行深度优先搜索，如果数组dp\[i\]\[j\]不为0，那么说明当前单元格b已经被计算过，因为以单元格b为起点的递增路径，也为单元格a的递增路径的一部分，所以我们可以直接使用这个计算结果，算出单元格a的递增路径的长度，然后用fmax函数经过比较来得出最长递增路径。遍历完矩阵中的所有单元格之后，即可得到矩阵中的最长递增路径的长度。

提交的代码：

int a[4][2]={
       {-1,0},{1,0},{0,1},{0,-1}};
    int  dfs(int **matrix,int m,int n,int x,int y,int**dp){
        if(dp[x][y]!=0){
            return dp[x][y];
        }
        dp[x][y]++;
         for(int k=0;k<4;k++){
             int xx=x+a[k][0];
             int yy=y+a[k][1];
             if(xx>=0&&xx<m&&yy>=0&&yy<n&&matrix[x][y]<matrix[xx][yy]){
                  dp[x][y]=fmax(dp[x][y],dfs(matrix,m,n,xx,yy,dp)+1);
             }
         }
         return dp[x][y];
    }
    int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize){
        if(matrix==NULL)
           return 0;
         int m=matrixSize,n=matrixColSize[0],i=0,j=0;
         int** dp = (int**)malloc(sizeof(int*) * m);
        for (int i = 0; i < m; i++) {
            dp[i] = (int*)malloc(sizeof(int) * n);
            memset(dp[i], 0, sizeof(int) * n);
        }
        int ans=0;
         for(i=0;i<m;i++){
             for(j=0;j<n;j++){
                 ans=fmax(ans,dfs(matrix,m,n,i,j,dp));
             }
         }
         return ans;
    }

[56c6547292da4f38bfb81f161ec24c9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4e7349877f834cfdb8174e196681b889.png