🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n\n\n---\n\n# Intuition\nThe problem requires moving from any cell in the first column to the rightmost column of a grid by only stepping to adjacent rightwa
![image.png](https://assets.leetcode.com/users/images/8f7c29ef-85fc-4a50-bb9f-e5da3f1edd48_1730190517.1314318.png)\n\n\n\n---\n\n# Intuition\nThe problem requires moving from any cell in the first column to the rightmost column of a grid by only stepping to adjacent rightward cells (right, diagonal up-right, or diagonal down-right) with increasing values. Memoization optimizes performance by storing results of subproblems.\n\n# Approach\n1. **Initialize Memoization Table**: Use a memo table initialized to `-1` to store the maximum number of moves starting from each cell.\n2. **Recursive Helper Function**:\n   - If the current cell has a precomputed value, return it.\n   - Otherwise, calculate the maximum moves by trying all possible rightward moves:\n      - Right, diagonal up-right, and diagonal down-right, ensuring that each destination cell has a larger value.\n3. **Update Maximum Moves**: For each cell in the first column, calculate and update the maximum possible moves across the grid.\n\n# Complexity\n- **Time Complexity**: \\(O(m \\times n)\\), where \\(m\\) is the number of rows and \\(n\\) is the number of columns.\n- **Space Complexity**: \\(O(m \\times n)\\), due to the memoization table.\n\n---\n\n# Code\n\n```dart []\nclass Solution {\n  int maxMoves(List<List<int>> grid) {\n    int rows = grid.length;\n    int cols = grid[0].length;\n    List<List<int>> memo = List.generate(rows, (_) => List.filled(cols, -1));\n    int maxMoves = 0;\n\n    for (int r = 0; r < rows; r++) {\n      maxMoves = max(maxMoves, getMoves(grid, r, 0, memo));\n    }\n\n    return maxMoves;\n  }\n\n  int getMoves(List<List<int>> grid, int r, int c, List<List<int>> memo) {\n    int rows = grid.length;\n    int cols = grid[0].length;\n    if (r < 0 || r >= rows || c >= cols) return 0;\n    if (memo[r][c] != -1) return memo[r][c];\n\n    int currentValue = grid[r][c];\n    int maxMoveCount = 0;\n\n    if (c + 1 < cols && grid[r][c + 1] > currentValue) {\n      maxMoveCount = max(maxMoveCount, 1 + getMoves(grid, r, c + 1, memo));\n    }\n    if (r - 1 >= 0 && c + 1 < cols && grid[r - 1][c + 1] > currentValue) {\n      maxMoveCount = max(maxMoveCount, 1 + getMoves(grid, r - 1, c + 1, memo));\n    }\n    if (r + 1 < rows && c + 1 < cols && grid[r + 1][c + 1] > currentValue) {\n      maxMoveCount = max(maxMoveCount, 1 + getMoves(grid, r + 1, c + 1, memo));\n    }\n\n    memo[r][c] = maxMoveCount;\n    return maxMoveCount;\n  }\n\n  int max(int a, int b) => (a > b) ? a : b;\n}\n```\n\n```java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int rows = grid.length;\n        int cols = grid[0].length;\n        int[][] memo = new int[rows][cols];\n        for (int[] row : memo) Arrays.fill(row, -1);\n        int maxMoves = 0;\n\n        for (int r = 0; r < rows; r++) {\n            maxMoves = Math.max(maxMoves, getMoves(grid, r, 0, memo));\n        }\n\n        return maxMoves;\n    }\n\n    private int getMoves(int[][] grid, int r, int c, int[][] memo) {\n        int rows = grid.length;\n        int cols = grid[0].length;\n        if (r < 0 || r >= rows || c >= cols) return 0;\n        if (memo[r][c] != -1) return memo[r][c];\n\n        int currentValue = grid[r][c];\n        int maxMoveCount = 0;\n\n        if (c + 1 < cols && grid[r][c + 1] > currentValue) {\n            maxMoveCount = Math.max(maxMoveCount, 1 + getMoves(grid, r, c + 1, memo));\n        }\n        if (r - 1 >= 0 && c + 1 < cols && grid[r - 1][c + 1] > currentValue) {\n            maxMoveCount = Math.max(maxMoveCount, 1 + getMoves(grid, r - 1, c + 1, memo));\n        }\n        if (r + 1 < rows && c + 1 < cols && grid[r + 1][c + 1] > currentValue) {\n            maxMoveCount = Math.max(maxMoveCount, 1 + getMoves(grid, r + 1, c + 1, memo));\n        }\n\n        memo[r][c] = maxMoveCount;\n        return maxMoveCount;\n    }\n}\n```\n\n\n```python []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        rows, cols = len(grid), len(grid[0])\n        memo = [[-1] * cols for _ in range(rows)]\n        max_moves = 0\n\n        def get_moves(r, c):\n            if r < 0 or r >= rows or c >= cols:\n                return 0\n            if memo[r][c] != -1:\n                return memo[r][c]\n            \n            current_value = grid[r][c]\n            max_move_count = 0\n\n            if c + 1 < cols and grid[r][c + 1] > current_value:\n                max_move_count = max(max_move_count, 1 + get_moves(r, c + 1))\n            if r - 1 >= 0 and c + 1 < cols and grid[r - 1][c + 1] > current_value:\n                max_move_count = max(max_move_count, 1 + get_moves(r - 1, c + 1))\n            if r + 1 < rows and c + 1 < cols and grid[r + 1][c + 1] > current_value:\n                max_move_count = max(max_move_count, 1 + get_moves(r + 1, c + 1))\n\n            memo[r][c] = max_move_count\n            return max_move_count\n\n        for r in range(rows):\n            max_moves = max(max_moves, get_moves(r, 0))\n\n        return max_moves\n```\n\n```cpp []\n#include <vector>\n#include <algorithm>\n\nclass Solution {\npublic:\n    int maxMoves(std::vector<std::vector<int>>& grid) {\n        int rows = grid.size(), cols = grid[0].size();\n        std::vector<std::vector<int>> memo(rows, std::vector<int>(cols, -1));\n        int maxMoves = 0;\n\n        for (int r = 0; r < rows; ++r) {\n            maxMoves = std::max(maxMoves, getMoves(grid, r, 0, memo));\n        }\n\n        return maxMoves;\n    }\n\nprivate:\n    int getMoves(const std::vector<std::vector<int>>& grid, int r, int c, std::vector<std::vector<int>>& memo) {\n        int rows = grid.size(), cols = grid[0].size();\n        if (r < 0 || r >= rows || c >= cols) return 0;\n        if (memo[r][c] != -1) return memo[r][c];\n\n        int currentValue = grid[r][c];\n        int maxMoveCount = 0;\n\n        if (c + 1 < cols && grid[r][c + 1] > currentValue) {\n            maxMoveCount = std::max(maxMoveCount, 1 + getMoves(grid, r, c + 1, memo));\n        }\n        if (r - 1 >= 0 && c + 1 < cols && grid[r - 1][c + 1] > currentValue) {\n            maxMoveCount = std::max(maxMoveCount, 1 + getMoves(grid, r - 1, c + 1, memo));\n        }\n        if (r + 1 < rows && c + 1 < cols && grid[r + 1][c + 1] > currentValue) {\n            maxMoveCount = std::max(maxMoveCount, 1 + getMoves(grid, r + 1, c + 1, memo));\n        }\n\n        memo[r][c] = maxMoveCount;\n        return maxMoveCount;\n    }\n};\n```\n\n\n```javascript []\nvar maxMoves = function(grid) {\n    const rows = grid.length;\n    const cols = grid[0].length;\n    const memo = Array.from({ length: rows }, () => Array(cols).fill(-1));\n    let maxMoves = 0;\n\n    for (let r = 0; r < rows; r++) {\n        maxMoves = Math.max(maxMoves, getMoves(grid, r, 0, memo));\n    }\n\n    return maxMoves;\n};\n\nfunction getMoves(grid, r, c, memo) {\n    const rows = grid.length;\n    const cols = grid[0].length;\n    if (r < 0 || r >= rows || c >= cols) return 0;\n    if (memo[r][c] !== -1) return memo[r][c];\n\n    const currentValue = grid[r][c];\n    let maxMoveCount = 0;\n\n    // Right\n    if (c + 1 < cols && grid[r][c + 1] > currentValue) {\n        maxMoveCount = Math.max(maxMoveCount, 1 + getMoves(grid, r, c + 1, memo));\n    }\n    // Diagonal Right-Up\n    if (r - 1 >= 0 && c + 1 < cols && grid[r - 1][c + 1] > currentValue) {\n        maxMoveCount = Math.max(maxMoveCount, 1 + getMoves(grid, r - 1, c + 1, memo));\n    }\n    // Diagonal Right-Down\n    if (r + 1 < rows && c + 1 < cols && grid[r + 1][c + 1] > currentValue) {\n        maxMoveCount = Math.max(maxMoveCount, 1 + getMoves(grid, r + 1, c + 1, memo));\n    }\n\n    memo[r][c] = maxMoveCount;\n    return maxMoveCount;\n}\n```\n\n\n\n\n```go []\npackage main\n\nimport "math"\n\nfunc maxMoves(grid [][]int) int {\n    rows, cols := len(grid), len(grid[0])\n    memo := make([][]int, rows)\n    for i := range memo {\n        memo[i] = make([]int, cols)\n        for j := range memo[i] {\n            memo[i][j] = -1\n        }\n    }\n\n    maxMoves := 0\n    for r := 0; r < rows; r++ {\n        maxMoves = int(math.Max(float64(maxMoves), float64(getMoves(grid, r, 0, memo))))\n    }\n\n    return maxMoves\n}\n\nfunc getMoves(grid [][]int, r, c int, memo [][]int) int {\n    rows, cols := len(grid), len(grid[0])\n    if r < 0 || r >= rows || c >= cols {\n        return 0\n    }\n    if memo[r][c] != -1 {\n        return memo[r][c]\n    }\n\n    currentValue := grid[r][c]\n    maxMoveCount := 0\n\n    if c+1 < cols && grid[r][c+1] > currentValue {\n        maxMoveCount = int(math.Max(float64(maxMoveCount), 1+float64(getMoves(grid, r, c+1, memo))))\n    }\n    if r-1 >= 0 && c+1 < cols && grid[r-1][c+1] > currentValue {\n        maxMoveCount = int(math.Max(float64(maxMoveCount), 1+float64(getMoves(grid, r-1, c+1, memo))))\n    }\n    if r+1 < rows && c+1 < cols && grid[r+1][c+1] > currentValue {\n        maxMoveCount = int(math.Max(float64(maxMoveCount), 1+float64(getMoves(grid, r+1, c+1, memo))))\n    }\n\n    memo[r][c] = maxMoveCount\n    return maxMoveCount\n}\n```\n\n\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Dynamic Programming', 'C', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']