Easiest solution with dfs everyone can understand-100% Beats
Intuition\n Describe your first thoughts on how to solve this problem. \nBeats 100%\n\n\n# Approach\n Describe your approach to solving the problem. \n### Probl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBeats 100%\n![Screenshot 2024-10-29 065344.png](https://assets.leetcode.com/users/images/3441dfb7-431a-4833-bbdf-8d52728e8206_1730166083.9584837.png)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n### Problem Statement\nGiven a 2D grid of integers, the goal is to determine the maximum number of moves you can make starting from any cell in the leftmost column. A move is valid if you can move to a cell directly to the right, down-right, or up-right, and the value of the next cell must be greater than the current cell.\n\n### Approach Explanation\n\n1. *Initialization*:\n   - The dimensions of the grid are obtained using rows and cols.\n   - A variable max is initialized to keep track of the maximum number of moves found.\n   - A 2D array memo is created for memoization, initialized to -1, to store results of previously computed states.\n   - An array directions is defined to represent the three possible moves: up-right, straight-right, and down-right.\n\n2. *Iterating Over Starting Points*:\n   - A loop iterates through each cell in the leftmost column (column index 0). For each cell, it calls the helper function dp to compute the maximum number of moves starting from that cell.\n\n3. *Dynamic Programming Helper Function*:\n   - The function dp(r, c) calculates the maximum moves possible starting from the cell at row r and column c.\n   - If the value in memo[r][c] is -1, indicating that this state has not been computed yet, it initializes memo[r][c] to 0.\n\n4. *Exploring Possible Moves*:\n   - For each potential move defined in directions, it calculates the new row (newR) and column (newC).\n   - If the new cell is within bounds and has a value greater than the current cell, it recursively calls dp(newR, newC) to compute the moves possible from that cell.\n   - The maximum moves from the current cell are updated based on the results of the recursive calls.\n\n5. *Early Exit Condition*:\n   - If at any point the maximum moves reach cols - 1 (indicating that a move to the last column is possible), the function returns early to optimize performance.\n\n6. *Final Output*:\n   - After evaluating all starting positions in the first column, the maximum number of moves found is returned.\n\n### Complexity Analysis\n- *Time Complexity*: O(rows * cols). Each cell is computed at most once due to memoization, leading to a linear traversal of the grid.\n- *Space Complexity*: O(rows * cols). The memo array requires space proportional to the number of cells in the grid.\n\n### Example\nConsider a grid:\n\n[\n  [1, 2, 3],\n  [4, 5, 6],\n  [7, 8, 9]\n]\n\nStarting from the cell (0,0), valid moves can be made to (1,1) and further to (2,2), leading to a maximum of 2 moves. The function will compute this for each cell in the first column, ultimately returning the highest count.\n\n### Conclusion\nThis approach efficiently calculates the maximum number of moves by leveraging dynamic programming and memoization. It explores all potential paths while avoiding redundant calculations, ensuring that the solution is both effective and efficient.\n\n# Complexity\n- Time complexity:O(N*M)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N*M)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```javascript []\n/**\n * @param {number[][]} grid\n * @return {number}\n */\nvar maxMoves = function(grid) {\n    let n = grid.length;\n    let m = grid[0].length;\n     let memo = Array.from({ length: n }, () => Array(m).fill(-1));\n    function maxMovesInGrid(i, j, prev, count) {\n        // Boundary check and comparison with previous cell value\n        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] <= prev) {\n            return count;\n        }\n\n        // Store current cell\'s value and mark it as visited\n        if(memo[i][j]!==-1) return memo[i][j]\n        let temp = grid[i][j];\n        grid[i][j] = -1;  // Mark as visited\n\n        // Recursive calls in three directions\n        let moves = Math.max(\n            maxMovesInGrid(i - 1, j + 1, temp, count + 1),\n            maxMovesInGrid(i, j + 1, temp, count + 1),\n            maxMovesInGrid(i + 1, j + 1, temp, count + 1)\n        );\n        memo[i][j]=moves\n        // Restore cell\'s value after recursion\n        grid[i][j] = temp;\n        return moves;\n    }\n\n    let ans = 0;\n    for (let i = 0; i < n; i++) {\n            ans = Math.max(ans, maxMovesInGrid(i, 0, -1, -1));\n    }\n\n    return ans;\n};\n```\n\n```python []\nfrom typing import List\n\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        n = len(grid)\n        m = len(grid[0])\n        memo = [[-1] * m for _ in range(n)]\n\n        def maxMovesInGrid(i, j, prev, count):\n            # Boundary check and comparison with previous cell value\n            if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] <= prev:\n                return count\n\n            # Check memoized result\n            if memo[i][j] != -1:\n                return memo[i][j]\n\n            # Store current cell\'s value and mark as visited\n            temp = grid[i][j]\n            grid[i][j] = -1  # Mark as visited\n\n            # Recursive calls in three directions\n            moves = max(\n                maxMovesInGrid(i - 1, j + 1, temp, count + 1),\n                maxMovesInGrid(i, j + 1, temp, count + 1),\n                maxMovesInGrid(i + 1, j + 1, temp, count + 1)\n            )\n            memo[i][j] = moves  # Store result in memo\n\n            # Restore cell\'s value after recursion\n            grid[i][j] = temp\n            return moves\n\n        ans = 0\n        for i in range(n):\n            ans = max(ans, maxMovesInGrid(i, 0, -1, -1))\n\n        return ans\n```
['Depth-First Search', 'Python3', 'JavaScript']