Easy C++ Solution || Optimized DP Memoization Solution for Maximum Moves in a Grid
Intuition\nThe problem can be approached by exploring each cell in the first column and recursively finding the longest valid path from that starting point. Usi
# Intuition\nThe problem can be approached by exploring each cell in the first column and recursively finding the longest valid path from that starting point. Using memoization optimizes this recursive approach by storing results of previously computed paths, which avoids redundant calculations.\n\n# Approach\n1. **Initialize DP Array:** Create a dp array where `dp[i][j]` holds the maximum path length from cell `(i, j)`.\n2. **Recursive Function with Memoization:** Define `f(i, j, m, n, grid, dp)`, which recursively calculates the longest path from `(i, j)` by exploring moves up-right, right, and down-right. If `dp[i][j]` is already filled, return it to avoid recomputation.\n3. **Traverse First Column:** For each cell in the first column, compute the longest path starting from that cell and update the global maximum.\n4. **Base Case:** Return `0` if the cell is out of bounds or use the cached result in dp if it\u2019s already computed.\n\n\n# Complexity\n- Time complexity: `O(m\xD7n)`\n\n- Space complexity: `O(m\xD7n)`\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int m=grid.size();\n        int n=grid[0].size();\n        int maxMoves=0;\n        vector<vector<int>>dp(m,vector<int>(n,-1));\n        for(int i=0;i<m;i++){\n            maxMoves=max(maxMoves,f(i,0,m,n,grid,dp));\n        }\n        return maxMoves;\n    }\n    int f(int i,int j,int m,int n,vector<vector<int>>& grid,vector<vector<int>>&dp){\n        if(i<0 || j<0 || i>=m || j>=n){\n            return 0;\n        }\n        if(dp[i][j]!=-1){\n            return dp[i][j];\n        }\n        int up=0,r=0,down=0;\n        if(i>0 && j<n-1 && grid[i-1][j+1]>grid[i][j]){\n          up=1+f(i-1,j+1,m,n,grid,dp);\n        }\n        if(j<n-1 && i<m-1 && grid[i+1][j+1]>grid[i][j]){\n          down=1+f(i+1,j+1,m,n,grid,dp);\n        }\n        if(j<n-1 && grid[i][j+1]>grid[i][j]){\n          r=1+f(i,j+1,m,n,grid,dp);\n        }\n        return dp[i][j]=max(up,max(down,r));\n    }\n};\n```
['Dynamic Programming', 'C++']