3 APPROACHES | DETAILED AND SIMPLE | MUST SEE FOR UNDERSTANDING
\n\n---\n\n## Approach 1: Simple Recursion\n\n### Intuition\n\nThe recursive approach checks each possible path by exploring three directions from each cell: di
\n\n---\n\n## Approach 1: Simple Recursion\n\n### Intuition\n\nThe recursive approach checks each possible path by exploring three directions from each cell: diagonal up-right, right, and diagonal down-right. If the next cell\'s value is greater than the current cell\'s, we count it as a move. The goal is to find the maximum number of such moves from the leftmost column to any cell in the grid.\n\n### Approach\n\n1. For each cell in the leftmost column, recursively find the maximum moves possible by moving only to cells with a higher value.\n2. Terminate the recursion if the row goes out of bounds or exceeds the last column.\n3. Explore three directions from each cell:\n   - Diagonal up-right\n   - Right\n   - Diagonal down-right\n4. Return the maximum moves found across all starting cells in the leftmost column.\n\n### Time Complexity\n\n- **O(3^n)**, where \\( n \\) is the number of columns, since each cell potentially calls three recursive functions.\n\n### Space Complexity\n\n- **O(n)** due to the recursive call stack depth.\n\n### Code\n\n```java\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int maxRow = grid.length - 1;\n        int maxCol = grid[0].length - 1;\n        int res = 0;\n\n        for (int i = 0; i <= maxRow; i++) {\n            int tempRes = recursion(grid, i, 0, maxRow, maxCol);\n            res = Math.max(res, tempRes);\n        }\n\n        return res;\n    }\n\n    int recursion(int[][] grid, int row, int col, int maxRow, int maxCol) {\n        if (row < 0 || col > maxCol || row > maxRow) return 0;\n\n        int diagonalUp = 0, right = 0, diagonalDown = 0;\n\n        if (row - 1 >= 0 && col + 1 <= maxCol && grid[row - 1][col + 1] > grid[row][col]) {\n            diagonalUp = 1 + recursion(grid, row - 1, col + 1, maxRow, maxCol);\n        }\n\n        if (col + 1 <= maxCol && grid[row][col + 1] > grid[row][col]) {\n            right = 1 + recursion(grid, row, col + 1, maxRow, maxCol);\n        }\n\n        if (row + 1 <= maxRow && col + 1 <= maxCol && grid[row + 1][col + 1] > grid[row][col]) {\n            diagonalDown = 1 + recursion(grid, row + 1, col + 1, maxRow, maxCol);\n        }\n\n        return Math.max(diagonalUp, Math.max(right, diagonalDown));\n    }\n}\n```\n\n### Test Case and Dry Run (Example)\n\n#### Input\n\n```plaintext\ngrid = [\n  [2, 4, 3, 5],\n  [5, 4, 9, 3],\n  [3, 4, 2, 11],\n  [10, 9, 13, 15]\n]\n```\n\n#### Diagram and Dry Run for Recursive Approach\n\nStart from each cell in the leftmost column and evaluate moves:\n\n1. Starting from cell `(0, 0)`:\n   - Moves to `(1, 1)`, then moves to `(2, 2)`.\n   - No further valid moves from `(2, 2)`.\n   - Max path length: 3 moves.\n\n2. Starting from cell `(1, 0)`:\n   - Moves to `(2, 1)`, then moves to `(3, 2)`.\n   - No further valid moves from `(3, 2)`.\n   - Max path length: 2 moves.\n\n3. The algorithm compares these paths to find the longest valid path: 3 moves.\n\n---\n\n## Approach 2: Iterative Dynamic Programming\n\n### Intuition\n\nInstead of using recursion, this approach uses a bottom-up DP table (`table`), where `table[row][col]` represents the maximum moves from the current cell to the last column. We calculate the values iteratively from the rightmost column to the leftmost.\n\n### Approach\n\n1. Initialize a DP table with dimensions equal to the grid.\n2. Start filling the DP table from the last column to the first column.\n3. For each cell in a column, calculate the maximum moves to reach cells in the next column.\n4. For cells in the leftmost column, update the result with the highest move count.\n\n### Time Complexity\n\n- **O(n * m)** where \\( n \\) is the number of rows and \\( m \\) is the number of columns.\n\n### Space Complexity\n\n- **O(n * m)** for the DP table.\n\n### Code\n\n```java\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int maxRow = grid.length - 1;\n        int maxCol = grid[0].length - 1;\n        int[][] table = new int[maxRow + 1][maxCol + 1];\n        int res = 0;\n\n        for (int col = maxCol; col >= 0; col--) {\n            for (int row = 0; row <= maxRow; row++) {\n                int diagonalUp = 0, right = 0, diagonalDown = 0;\n\n                if (row - 1 >= 0 && col + 1 <= maxCol && grid[row - 1][col + 1] > grid[row][col]) {\n                    diagonalUp = 1 + table[row - 1][col + 1];\n                }\n\n                if (col + 1 <= maxCol && grid[row][col + 1] > grid[row][col]) {\n                    right = 1 + table[row][col + 1];\n                }\n\n                if (row + 1 <= maxRow && col + 1 <= maxCol && grid[row + 1][col + 1] > grid[row][col]) {\n                    diagonalDown = 1 + table[row + 1][col + 1];\n                }\n\n                table[row][col] = Math.max(diagonalUp, Math.max(right, diagonalDown));\n                if (col == 0) res = Math.max(res, table[row][0]);\n            }\n        }\n\n        return res;\n    }\n}\n```\n\n---\n\n## Approach 3: Recursion + Memoization\n\n### Intuition\n\nThis approach combines recursion and memoization to avoid redundant calculations by caching previously computed values in a `memory` table. Each cell\'s maximum move count is stored after the first calculation, speeding up the recursive solution.\n\n### Approach\n\n1. Start from each cell in the leftmost column.\n2. Use recursion and memoization to find the maximum moves possible from each cell, caching results in `memory`.\n3. Return the maximum path found across all starting cells in the leftmost column.\n\n### Time Complexity\n\n- **O(n * m)** due to memoization, each cell is visited once.\n\n### Space Complexity\n\n- **O(n * m)** for the memoization table.\n\n### Code\n\n```java\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int maxRow = grid.length - 1;\n        int maxCol = grid[0].length - 1;\n        int[][] memory = new int[maxRow + 1][maxCol + 1];\n        \n        for (int[] row : memory) Arrays.fill(row, -1);\n\n        int res = 0;\n        for (int i = 0; i <= maxRow; i++) {\n            int tempRes = recursion(grid, i, 0, maxRow, maxCol, memory);\n            res = Math.max(res, tempRes);\n        }\n\n        return res;\n    }\n\n    int recursion(int[][] grid, int row, int col, int maxRow, int maxCol, int[][] memory) {\n        if (row < 0 || col > maxCol || row > maxRow) return 0;\n\n        if (memory[row][col] != -1) return memory[row][col];\n\n        int diagonalUp = 0, right = 0, diagonalDown = 0;\n\n        if (row - 1 >= 0 && col + 1 <= maxCol && grid[row - 1][col + 1] > grid[row][col]) {\n            diagonalUp = 1 + recursion(grid, row - 1, col + 1, maxRow, maxCol, memory);\n        }\n\n        if (col + 1 <= maxCol && grid[row][col + 1] > grid[row][col]) {\n            right = 1 + recursion(grid, row, col + 1, maxRow, maxCol, memory);\n        }\n\n        if (row + 1 <= maxRow && col + 1 <= maxCol && grid[row + 1][col + 1] > grid[row][col]) {\n            diagonalDown = 1 + recursion(grid, row + 1, col + 1, maxRow, maxCol, memory);\n        }\n\n        return memory[row][col] = Math.max(diagonalUp, Math.max(right, diagonalDown));\n    }\n}\n```\n\n![Screenshot from 2024-07-09 09-56-34.png](https://assets.leetcode.com/users/images/cf6a7ff6-0155-49c5-a595-2a842e2cb41b_1730196318.2444553.png)\n
['Dynamic Programming', 'Memoization', 'Matrix', 'Java']