Maximum Number of Moves in a Grid | DP | Memoization | | Tabulation | O(n) Space | O(n×m) Time
Intuition\nThe problem can be solved by navigating the grid while adhering to the rules of movement, where each cell we move to must have a strictly larger valu
# Intuition\nThe problem can be solved by navigating the grid while adhering to the rules of movement, where each cell we move to must have a strictly larger value than the previous cell. To maximize the number of moves, we aim to explore all potential paths starting from the first column of the grid and apply either a memoization or tabulation  _*(dynamic programming)*_ approach to store intermediate results for efficiency.\n\n# Approach 1: Memoization\n\n1. Recursive Definition: For each cell (i, j), define a recursive function rec() that explores three possible moves: right, up-right, and down-right, storing results in a memoization table (dp).\n2. Base Case and Bounds: If the cell (i, j) has already been visited, retrieve its stored result from dp. Check boundary conditions to avoid index overflow.\n3. Recursive Case: For each direction, verify if moving there increases the value, then make the recursive call. Track the maximum moves achievable.\n4. Final Calculation: Iterate over the first column cells and calculate the maximum number of moves from each.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time Complexity: O(n\xD7m)\n    Each cell (i, j) in the grid is visited once, and recursive results are cached. Thus, the complexity is proportional to the number of cells in the grid.\n- Space Complexity: O(n\xD7m) \n    For the dp matrix used to store intermediate results.\n\n# Code\n``` Cpp []\nclass Solution {\npublic:\n    int rec(vector<vector<int>> &grid, int i, int j, int n, int m, vector<vector<int>> &dp){\n        if(dp[i][j] != -1){\n            return dp[i][j];\n        }\n        int row[3] = {-1, 0, 1};  // movement options for rows: up-right, right, down-right\n        int col[3] = {1, 1, 1};   // all moves are to the right column\n        int ans = 0;\n\n        // Explore all possible moves from (i, j)\n        for(int k = 0; k < 3; k++){\n            int r = i + row[k];\n            int c = j + col[k];\n            if(r >= 0 && r < n && c < m && grid[r][c] > grid[i][j]){ // move to a higher value cell\n                ans = max(ans, 1 + rec(grid, r, c, n, m, dp));  // count the move and recurse\n            }\n        }\n        return dp[i][j] = ans;  // store result in dp and return\n    }\n\n    int maxMoves(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        vector<vector<int>> dp(n, vector<int>(m, -1));  // memoization table\n        int maxi = 0;\n\n        // Start from each cell in the first column and get the maximum moves\n        for(int i = 0; i < n; i++){\n            maxi = max(maxi, rec(grid, i, 0, n, m, dp));\n        }\n        return maxi;\n    }\n};\n\n```\n``` Python []\nclass Solution:\n    def rec(self, grid, i, j, n, m, dp):\n        if dp[i][j] != -1:\n            return dp[i][j]\n        row = [-1, 0, 1]\n        col = [1, 1, 1]\n        ans = 0\n\n        # Explore all possible moves from (i, j)\n        for k in range(3):\n            r, c = i + row[k], j + col[k]\n            if 0 <= r < n and c < m and grid[r][c] > grid[i][j]:\n                ans = max(ans, 1 + self.rec(grid, r, c, n, m, dp))\n        dp[i][j] = ans\n        return ans\n\n    def maxMoves(self, grid):\n        n, m = len(grid), len(grid[0])\n        dp = [[-1] * m for _ in range(n)]\n        maxi = 0\n\n        for i in range(n):\n            maxi = max(maxi, self.rec(grid, i, 0, n, m, dp))\n        return maxi\n```\n- \n# Approach 2: Tabulation\n\n1. Dynamic Programming Array: Maintain a dp array where each element represents the maximum moves reachable in each row.\n2. Iterate Through Columns: Move column by column from left to right, updating dp based on accessible moves. For each cell (i, j), check the conditions to move to each of the three allowed directions.\n3. Track Maximum Moves: As we update dp, store the furthest column reached for cells with positive moves.\n\n# Complexity\n- Time Complexity: O(n\xD7m)\n    Each cell in the grid is iteratively processed only once, resulting in a complexity of O(n\xD7m).\n- Space Complexity: O(n) \n    As only a 1D array dp of size n is used for storing maximum moves possible from each row.\n\n# Code\n``` Cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        vector<int> dp(n, 1);  // initially, each row can make at least 1 move\n        int maxi = 0;\n\n        for(int j = 1; j < m; j++) {\n            int up = dp[0];\n            dp[0] = max((grid[0][j] > grid[0][j-1] ? dp[0] : 0), \n                        (grid[0][j] > grid[1][j-1] ? dp[1] : 0));\n            if(dp[0] > 0) maxi = j;\n\n            for(int i = 1; i < n-1; i++) {\n                int temp = dp[i];\n                dp[i] = max({grid[i][j] > grid[i][j-1] ? dp[i] : 0,\n                             grid[i][j] > grid[i-1][j-1] ? up : 0,\n                             grid[i][j] > grid[i+1][j-1] ? dp[i+1] : 0});\n                up = temp;\n                if(dp[i] > 0) maxi = j;\n            }\n\n            dp[n-1] = max((grid[n-1][j] > grid[n-1][j-1] ? dp[n-1] : 0), \n                          (grid[n-1][j] > grid[n-2][j-1] ? up : 0));\n            if(dp[n-1] > 0) maxi = j;\n        }\n\n        return maxi;\n    }\n};\n\n```\n``` Python []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        n, m = len(grid), len(grid[0])\n        dp = [1] * n  # initial moves possible for each row\n        maxi = 0\n\n        for j in range(1, m):\n            up = dp[0]\n            dp[0] = max((grid[0][j] > grid[0][j-1] and dp[0] or 0),\n                        (grid[0][j] > grid[1][j-1] and dp[1] or 0))\n            if dp[0] > 0: maxi = j\n\n            for i in range(1, n - 1):\n                temp = dp[i]\n                dp[i] = max((grid[i][j] > grid[i][j-1] and dp[i] or 0),\n                            (grid[i][j] > grid[i-1][j-1] and up or 0),\n                            (grid[i][j] > grid[i+1][j-1] and dp[i+1] or 0))\n                up = temp\n                if dp[i] > 0: maxi = j\n\n            dp[n-1] = max((grid[n-1][j] > grid[n-1][j-1] and dp[n-1] or 0),\n                          (grid[n-1][j] > grid[n-2][j-1] and up or 0))\n            if dp[n-1] > 0: maxi = j\n\n        return maxi\n```\n\n# \uD83D\uDD3C Upvote Please \uD83D\uDE80\uD83D\uDC4D #
['C++']