Memoization solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe task requires finding the maximum number of moves we can make in a grid starting fr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe task requires finding the maximum number of moves we can make in a grid starting from any cell in the first column, with constraints on the moves: only move to a cell in the next column to the right, and the value of that cell must be greater than the current cell. The problem thus involves finding the longest increasing path starting from any cell in the first column. To avoid recalculating paths from the same cells multiple times, memoization is used.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nRecursive Function with Memoization:\n\nDefine a recursive helper function call(row, col, grid, dp) that calculates the maximum moves possible starting from cell (row, col).\nUse a dp table to store results for each cell. If a cell has been computed before, return its stored result to avoid recomputation.\nMovement Rules:\n\nFrom a cell (row, col), you can move:\nRight to (row, col + 1)\nDiagonally up-right to (row - 1, col + 1)\nDiagonally down-right to (row + 1, col + 1)\nOnly move if the value in the target cell is strictly greater than the current cell\u2019s value.\nFinding the Maximum Path:\n\nIterate through all cells in the first column, calling call(i, 0, grid, dp) for each row i.\nTrack and return the maximum result across all possible starting cells.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m\xD7n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m\xD7n)\n# Code\n```cpp []\nclass Solution {\npublic:\n\n   int call(int row,int col,vector<vector<int>>& grid,vector<vector<int>> &dp){\n    if (row >= grid.size() || col >= grid[0].size() || row < 0) {\n           return 0;\n       }\n       \n       if(dp[row][col]!=-1){\n        return dp[row][col];\n       }\n       int nnrow = row - 1;\n       int ncol = col + 1;\n       int nrow = row + 1;\n       int ans = 0;\n       \n       // Move downward\n       if (nrow < grid.size() && ncol <grid[0].size()  && grid[nrow][ncol] > grid[row][col]) {\n           ans = max(ans, 1 + call(nrow, ncol, grid,dp));\n       }\n       \n       // Move right\n       if (ncol < grid[0].size() && grid[row][ncol] > grid[row][col]) {\n           ans = max(ans, 1 + call(row,ncol, grid,dp));\n       }\n       \n       // Move upward\n       if (nnrow >= 0  && ncol < grid[0].size() && grid[nnrow][ncol] > grid[row][col]) {\n           ans = max(ans, 1 + call(row - 1, col+1, grid,dp));\n       }\n       \n    return dp[row][col]=ans;\n\n   }\n \n    int maxMoves(vector<vector<int>>& grid) {\n        int ans = 0;\n        int n= grid.size();\n        int m =grid[0].size();\n        vector<vector<int>> dp(n, vector<int> (m,-1));\n        for(int i=0;i<grid.size();i++){\n        ans = max(ans,call(i,0,grid,dp));\n        }\n        return ans;\n    }\n};\n```
['C++']