329.行列内の最長インクリメントパス

問題のタイプ:記憶化の再帰的な難易度を深く検索します:困難な問題の意味:1つの2次元のマトリックスの中から1つの厳格に増加する経路を見つけます.深度検索を使用すると、タグは必要ありません.現在の点までは元の点よりも大きな値を満たす必要があるため、繰り返しは行われません.次に、記憶化再帰記録を使用して最も長いパスを記録し、計算済みであれば直接戻ります.備考:2020.4.18バイトジャンプ三面試験問題.面接官は私に遡及を使うように指示したが、実際には必要ない.この条件を増やしてある点を繰り返すことはできないからだ.

class Solution {
public:
    int m, n;
    vector<vector<int>> mp;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        if(!m) return 0;
        n = matrix[0].size();
        mp = vector<vector<int>> (m, vector<int>(n, -1));
        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                res = max(res, dfs(i, j, matrix));
            }
        }
        return res;
    }
    int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
    int dfs(int x, int y, vector<vector<int>>& matrix){
        if(mp[x][y] != -1) return mp[x][y];
        mp[x][y] = 1;
        //                                          
        for(int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < m && b >= 0 && b < n && matrix[a][b] > matrix[x][y]){
                mp[x][y] = max(mp[x][y], 1 + dfs(a, b, matrix));
            }
        }
        return mp[x][y];
    }
};