仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

矩阵中的最长递增路径

发表于 更新于 分类于 ，
本文字数： 1.1k 阅读时长 ≈ 1 分钟

【道德经·第三十四章】大道汜兮，其可左右。万物恃之以生而不辞，功成而不有。衣养万物而不为主，常无欲，可名于小；万物归焉而不为主，可名为大。以其终不自为大，故能成其大。

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

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
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int m = 0, n = 0;
int longestIncreasingPath(vector<vector<int>>& matrix) {
    m = matrix.size();
    n = matrix[0].size();
    
    vector<vector<int> > dp(m, vector<int>(n, 0));
    
    int ans = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            ans = max(ans, dfs(matrix, i, j, dp));
        }
    }
    
    return ans;
}

int dfs(vector<vector<int> >& matrix, int i, int j, vector<vector<int> >& dp) {
    if(dp[i][j] != 0) {
        return dp[i][j];
    }
    
    dp[i][j]++;
    for(int k = 0; k < 4; k++) {
        int nexti = i+dirs[k][0];
        int nextj = j+dirs[k][1];
        
        if(nexti>=0 && nexti<m && nextj>=0 && nextj<n && matrix[nexti][nextj]>matrix[i][j]) {
            dp[i][j] = max(dp[i][j], dfs(matrix, nexti, nextj, dp)+1);
        }
    }
    
    return dp[i][j];
}

位我上者，灿烂星空；道德律令，在我心中。