力扣题目
329. 矩阵中的最长递增路径
题目描述：
解题思路：
看到这题，往上，下，左，右四个方向移动单元格，我的第一反应是运用深度优先搜索，但是单单使用到深度优先搜索的结果会超出时间限制，时间复杂度过高，进行了大量的重复运算，所以这道题还需要运用动态规划来进行优化，存储以前面单元格为起点的最长递增路径的长度，减少重复的计算。
先设置数组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;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/95969.html
