🧑‍💻Java Recursive Approach || ⚡Runtime 5 ms
\n\n\n# Intuition\nThe problem requires finding the maximum number of moves starting from any cell in the first column of a grid, moving to the right and ensuri
![image.png](https://assets.leetcode.com/users/images/73e6d368-f485-4004-b26b-7031bdefe654_1730179308.885108.png)\n\n\n# Intuition\nThe problem requires finding the maximum number of moves starting from any cell in the first column of a grid, moving to the right and ensuring each move is to a cell with a strictly greater value than the current cell. This can be approached using dynamic programming to store the maximum moves for each cell and avoid redundant calculations.\n\n# Approach\n1. **Initialization**: \n   - Initialize a 2D array `dp` where `dp[i][j]` stores the maximum number of moves starting from cell `(i, j)`.\n   - Initialize dimensions `n` and `m` for the grid.\n\n2. **Recursive Function `f`**:\n   - Define a recursive function `f(i, j, prev, grid)` that computes the maximum number of moves starting from cell `(i, j)` with a previous value `prev`.\n   - Base cases:\n     - If `(i, j)` is out of bounds, return 0.\n     - If the current cell value `x` is not greater than `prev`, return 0.\n     - If `dp[i][j]` is already computed, return `dp[i][j]`.\n   - Recursive cases:\n     - Compute the maximum moves by considering moves to the top-right, right, and bottom-right cells.\n     - Store the result in `dp[i][j]`.\n\n3. **Main Function `maxMoves`**:\n   - Initialize the `dp` array with `-1`.\n   - Iterate through each cell in the first column and compute the maximum moves using the recursive function `f`.\n   - Return the maximum value found minus one because the initial call to `f` starts with a move count of 1.\n\n# Complexity\n- **Time complexity**: \n  - The time complexity is $$O(n \\times m)$$, where `n` is the number of rows and `m` is the number of columns. Each cell is processed once, and the recursive function explores possible moves.\n\n- **Space complexity**: \n  - The space complexity is $$O(n \\times m)$$ due to the `dp` array storing results for each cell.\n\n\n# Code\n```java []\nimport java.util.Arrays;\n\nclass Solution {\n    int[][] dp;\n    int n, m;\n\n    public int f(int i, int j, int prev, int[][] grid) {\n        if (i < 0 || j < 0 || i >= n || j >= m) return 0;\n        int x = grid[i][j];\n        if (x <= prev) return 0;\n        if (dp[i][j] != -1) return dp[i][j];\n\n        dp[i][j] = 1 + Math.max(Math.max(f(i - 1, j + 1, x, grid),\n                                         f(i, j + 1, x, grid)),\n                                f(i + 1, j + 1, x, grid));\n        return dp[i][j];\n    }\n\n    public int maxMoves(int[][] grid) {\n        n = grid.length;\n        m = grid[0].length;\n        dp = new int[n][m];\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n\n        int ans = 0;\n        for (int i = 0; i < n; i++) {\n            ans = Math.max(ans, f(i, 0, -1, grid));\n        }\n        return ans - 1;\n    }\n\n    // public static void main(String[] args) {\n    //     Solution solution = new Solution();\n    //     int[][] grid1 = {{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}};\n    //     int[][] grid2 = {{3, 2, 4}, {2, 1, 9}, {1, 1, 7}};\n    //     System.out.println(solution.maxMoves(grid1)); // Output: 3\n    //     System.out.println(solution.maxMoves(grid2)); // Output: 0\n    // }\n}\n```
['Array', 'Recursion', 'Matrix', 'Java']