Untitled
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