Clear DFS/DP solution


  • 0
    J

    '''

    class Solution {
    public:

    int dfs(vector<vector<int>> &matrix, vector<vector<int>> &f, int x, int y, int m, int n)
    {
        if (f[x][y] > 0) return f[x][y];
        f[x][y] = 1;
        static int dirs[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dirs[i][0], ny = y + dirs[i][1];
            if (nx >= m || nx < 0|| ny >= n || ny < 0) continue;
            if (matrix[nx][ny] < matrix[x][y]){
                f[x][y] = max(f[x][y], dfs(matrix, f, nx, ny, m, n) + 1);
            }
        }
        
        return f[x][y];
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        if (n == 0) return 0;
        vector<vector<int>> f(m, vector<int>(n, 0));
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                ret = max(ret, dfs(matrix, f, i, j, m, n));
            }
        }
        
        return ret;
    }
    

    };

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.