最长递增路径
题目
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
链接
DP
但是依旧不能覆盖所有的情况
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
vector<vector<int>>dp(m,vector<int>(n,1));
int ans=1;
//右-下
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i&&matrix[i-1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
}
if(j&&matrix[i][j-1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j-1]+1);
}
if(dp[i][j]>=ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
//左上
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(i+1<m&&matrix[i+1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i+1][j]+1);
}
if(j+1<n&&matrix[i][j+1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j+1]+1);
}
if(dp[i][j]>ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
//右-上
for(int i=0;i<m;i++){
for(int j=n-1;j>=0;j--){
if(i&&matrix[i-1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
}
if(j+1<n&&matrix[i][j+1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j+1]+1);
}
if(dp[i][j]>=ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
//左-下
for(int i=m-1;i>=0;i--){
for(int j=0;j<n;j++){
if(i+1<m&&matrix[i+1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i+1][j]+1);
}
if(j&&matrix[i][j-1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j-1]+1);
}
if(dp[i][j]>ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
/*---第二次--*/
//右-下
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i&&matrix[i-1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
}
if(j&&matrix[i][j-1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j-1]+1);
}
if(dp[i][j]>=ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
//左上
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(i+1<m&&matrix[i+1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i+1][j]+1);
}
if(j+1<n&&matrix[i][j+1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j+1]+1);
}
if(dp[i][j]>ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
//右-上
for(int i=0;i<m;i++){
for(int j=n-1;j>=0;j--){
if(i&&matrix[i-1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
}
if(j+1<n&&matrix[i][j+1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j+1]+1);
}
if(dp[i][j]>=ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
//左-下
for(int i=m-1;i>=0;i--){
for(int j=0;j<n;j++){
if(i+1<m&&matrix[i+1][j]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i+1][j]+1);
}
if(j&&matrix[i][j-1]<matrix[i][j]){
dp[i][j]=max(dp[i][j],dp[i][j-1]+1);
}
if(dp[i][j]>ans){
// printf("(%d ,%d),value=%d len=%d\n",i,j,matrix[i][j],dp[i][j]);
ans=dp[i][j];
}
}
}
return ans;
}
};
拓扑排序
如果一个单元格的值比它的所有相邻单元格的值都要大，那么这个单元格对应的最长递增路径是1
将矩阵看成一个有向图，计算每个单元格对应的出度，即有多少条边从该单元格出发。
位置(i,j)的出度等于其四个方向的四个单元格中，值大于(i,j)的单元格个数；
接着我们利用BFS进行拓扑排序，从出度为0的单元格开始，找到它们的入节点的位置，也就是比他们小的四周节点位置，更新这些新的节点的出度，将出度为0的再次加入队列
计算出队列的层数，即为最大的递增长度
class Solution {
public:
//拓扑排序
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
vector<vector<int>>outdegree(m,vector<int>(n,0));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
for(int k=0;k<4;k++){
int nx=dx[k]+i;
int ny=dy[k]+j;
if(nx>=0&&nx<m&&ny>=0&&ny<n&&matrix[nx][ny]>matrix[i][j]){
outdegree[i][j]++;
}
}
}
}
queue<pair<int,int>>nodes;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(outdegree[i][j]==0){
nodes.push({i,j});
}
}
}
//BFS
int ans=0;
while(!nodes.empty()){
ans++;
int size=nodes.size();
for(int i=0;i<size;i++){
auto [x,y]=nodes.front();
nodes.pop();
for(int k=0;k<4;k++){
int nx=dx[k]+x;
int ny=dy[k]+y;
if(nx>=0&&nx<m&&ny>=0&&ny<n&&matrix[nx][ny]<matrix[x][y]){
outdegree[nx][ny]--;
if(outdegree[nx][ny]==0){
nodes.push({nx,ny});
}
}
}
}
}
return ans;
}
};