矩阵中的最长递增路径-蒲公英云

矩阵中的最长递增路径

力扣题目

矩阵中的最长递增路径

题目描述：

解题思路：

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

先设置数组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;
}