Python | Dynamic Programming | Depth-First Search  &  Memoization
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get the dimens
[see the Successfully Accepted Submission](https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/submissions/1436761545/?envType=daily-question&envId=2024-10-29)\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get the dimensions of the grid\n        m, n = len(grid), len(grid[0])\n        \n        # Directions for possible moves: (row offset, col offset)\n        directions = [(-1, 1), (0, 1), (1, 1)]\n        \n        # Memoization cache to store the max moves from each cell\n        memo = {}\n        \n        # Helper function to perform DFS with memoization\n        def dfs(row, col):\n            # If we are at the last column, no further moves are possible\n            if col == n - 1:\n                return 0\n            # If already computed, return the stored result\n            if (row, col) in memo:\n                return memo[(row, col)]\n            \n            max_moves = 0\n            current_value = grid[row][col]\n            \n            # Check all possible moves\n            for dr, dc in directions:\n                new_row, new_col = row + dr, col + dc\n                # Check if the move is valid\n                if 0 <= new_row < m and 0 <= new_col < n and grid[new_row][new_col] > current_value:\n                    # Calculate moves from the next cell\n                    max_moves = max(max_moves, 1 + dfs(new_row, new_col))\n            \n            # Store the result in memo\n            memo[(row, col)] = max_moves\n            return max_moves\n        \n        # Try to start from each cell in the first column and find the max moves\n        result = 0\n        for i in range(m):\n            result = max(result, dfs(i, 0))\n        \n        return result\n\n```\n\n# Solution to Maximum Moves in a Grid Problem\n\n## Steps to Solve the Problem\n\n### 1. Define Possible Moves:\nFor any cell `(row, col)`, we can move:\n- **Diagonally up** to `(row - 1, col + 1)`\n- **Right** to `(row, col + 1)`\n- **Diagonally down** to `(row + 1, col + 1)`\n\nEach of these moves should only be allowed if:\n- The new cell is within grid boundaries.\n- The value of the new cell is strictly greater than the value of the current cell.\n\n### 2. Start from Any Cell in the First Column:\n- We need to try starting from each cell in the first column (column `0`).\n- From each starting point, find the maximum number of moves possible.\n\n### 3. Use DFS with Memoization:\n- Since the grid can be large, a memoized DFS can store already-computed results for each cell to avoid redundant calculations.\n- For each cell, store the maximum moves that can be made starting from that cell.\n\n### 4. Return the Maximum of All Starting Points:\n- We need the maximum value of moves obtained from any starting cell in the first column.\n\n## Explanation of the Code\n\n### Directions Array:\n- We define possible moves using the `directions` array to make the code cleaner.\n\n### Memoization Dictionary:\n- `memo` stores the maximum number of moves starting from each cell to avoid redundant calculations.\n\n### DFS Function:\n- The `dfs` function recursively computes the maximum moves possible from a given cell `(row, col)`.\n- For each valid move, it adds `1` to the result of the recursive call to `dfs` on the next cell.\n\n### Loop through Starting Points:\n- The main function iterates over each row of the first column (column `0`) to determine the maximum moves achievable from any starting cell.\n\n## Complexity Analysis\n\n- **Time Complexity**: \\(O(m \\times n)\\), where `m` is the number of rows and `n` is the number of columns, since each cell is processed once due to memoization.\n- **Space Complexity**: \\(O(m \\times n)\\) due to the memoization storage.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']