329. Longest Increasing Path in a Matrix

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

Posted by bbkgl on July 26, 2020

心似双丝网

中有千千结

虽然是每天刷一道题,但好几次都没时间写题解。。。

这道题算是dp的一种,一般从暴力的角度出发很容易想到dfs能直接获得每个点作为起始点得到的最长递增路径。

这样的话,对着每个点做一次暴力dfs,就得到答案了。

不过显然这样子会超时,复杂度差不多O((m * n)^2)。。。

仔细想想实际上,dfs在经过每个点的时候,无论是不是从这个点开始的,都能得到从这个点出发的最长递增路径。于是“记忆化搜索”这个东西就来了。

可以利用二维数组记住每次dfs到的点的最长递增路径,这样下次递归到这个点的时候,就不用再接着递归了。

class Solution {
private:
    static int dx[];
    static int dy[];

    inline bool check(vector<vector<int>> &g, int i, int j, int pre) {
        int m = g.size(), n = g[0].size();
        return 0 <= i && i < m && 0 <= j && j < n && pre < g[i][j];
    }

    int dfs(vector<vector<int>> &g, int x, int y, vector<vector<int>> &dist) {
        if (dist[x][y] != 0) return dist[x][y];
        dist[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (check(g, xx, yy, g[x][y])) {
                dist[x][y] = max(dist[x][y], 1 + dfs(g, xx, yy, dist));
            }
        }
        return dist[x][y];
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int>> dist(m, vector<int>(n, 0));
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] == 0)
                    ans = max(ans, dfs(matrix, i, j, dist));
            }
        }
        return ans;
    }
};

int Solution::dx[] = {0, 0, 1, -1};
int Solution::dy[] = {1, -1, 0, 0};