力扣题目
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; }
