题解 | #矩阵最长递增路径#

经典老题了，直接记忆化搜索即可。

class Solution {
public:
    int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
    int n, m, res = 0;
    vector<vector<int>> f;
    int solve(vector<vector<int> >& matrix) {
        // write code here
        n = matrix.size(), m = matrix[0].size();
        f = vector<vector<int>> (n, vector<int> (m, -1));
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) res = max(res, dfs(matrix, i, j));
        }

        return res;
    }
    int dfs(vector<vector<int>> &nums, int x,int y) {
        if(f[x][y] != -1) return f[x][y];
        int u = 1;
        for(int i=0;i<4;i++) {
            int newx = x + dir[i][0];
            int newy = y + dir[i][1];
            if(newx<0 || newx>=n || newy<0 || newy >=m) continue;
            if(nums[newx][newy] > nums[x][y]) {
                u = max(u, 1 + dfs(nums, newx, newy));
            }
        }
        f[x][y] = u;
        return u;
    }
};