Untitled

 avatar
unknown
plain_text
6 months ago
1.0 kB
5
Indexable
class Solution {
public:
    
    int dir[3] = {-1, 0 , 1};
    bool isValid(int i , int j, int N , int M) {
        if(i>=0 && j>=0 && i<N && j<M)return true;
        return false;
    }
    int solve(int i, int j , int N, int M , vector<vector<int>>& grid, vector<vector<int>>& dp){
        if(dp[i][j]!=-1)return dp[i][j];
        
        int ans = 0;
        
        for(int d: dir) {
            int row = i + d , col = j + 1;
            
            if(isValid(row, col, N, M)) {
                if(grid[row][col] > grid[i][j]) {
                        ans = max(ans , 1 + solve(row , col, N, M , grid, dp));
                }

            }
        }
        
        return dp[i][j] = ans;
    }
    int maxMoves(vector<vector<int>>& grid) {
        int N = grid.size(), M = grid[0].size(), ans = 0;
        vector<vector<int>> dp(N, vector<int>(M, -1));
        
        for(int i=0;i<N;i++) {
                ans = max(ans , solve(i , 0, N , M , grid, dp));
            
        }
        
        return ans;
    }
};
Editor is loading...
Leave a Comment