leetcode 329. Longest Increasing Path in a Matrix

Posted on | In , |

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums =

[

[9,9,4],

[6,6,8],

[2,1,1]

]

Output: 4

Explanation: The longest increasing path is [1, 2, 6,
9].

Example 2:

Input: nums =

[
[3,4,5],

[3,2,6],

[2,2,1]

]
Output: 4

Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

记忆化递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int m,n;
    vector<vector<int>> p;
    vector<vector<int >>dp;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m=matrix.size();
        if(m==0) return 0;
        n=matrix[0].size();
        dp=vector<vector<int >>(m,vector<int>(n,0));
        p.swap(matrix);
        int ans=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++ )
            {

                 ans=max(ans,dfs(i,j));
            }
           
            
        }
        return ans;
    }
    int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
    int dfs(int x,int y){
        if(dp[x][y]!=0) return dp[x][y];
        dp[x][y]=1;
        for(int i=0;i<4;i++){
            int newx=x+dir[i][0];
            int newy=y+dir[i][1];
            if(newx<0||newx>=m||newy<0||newy>=n) continue;
            if(p[newx][newy]<=p[x][y]) continue;
            dp[x][y]=max(dp[x][y],dfs(newx,newy)+1);
            
        }
        
        return dp[x][y];
    }
};