Java Solution for Maximum Number of Moves In a Grid Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is essentially about finding the longest path in a grid where each step mov
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is essentially about finding the longest path in a grid where each step moves to a cell with a strictly higher value. Starting from any cell in the first column, our goal is to determine the maximum number of moves we can make by only moving to the right, top-right, or bottom-right cells. This problem resembles finding paths in a directed acyclic graph (DAG) where cells are nodes, and each valid move is a directed edge.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tDFS with Memoization:\n\t\u2022\tWe use Depth-First Search (DFS) from each cell in the first column, exploring potential paths to find the longest path of moves.\n\t\u2022\tFor each cell, we can move in three directions: right, top-right, and bottom-right, but only if the destination cell has a higher value than the current cell.\n\t\u2022\tTo avoid recalculating paths from the same cell multiple times, we use a memo table. This table stores the maximum moves from each cell, saving time by reusing these results during subsequent DFS calls.\n2.\tInitialize and Track Maximum Moves:\n\t\u2022\tFor each cell in the first column, initiate DFS to explore potential moves and calculate the longest path.\n\t\u2022\tTrack the maximum path length found for all first-column cells.\n3.\tBoundary Conditions and Edge Cases:\n\t\u2022\tWe check if each move stays within the grid boundaries.\n\t\u2022\tIf no valid moves are possible, the function returns 0\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m x n):\n\u2022\tEach cell is processed once due to memoization, where m is the number of rows and n is the number of columns.\n\u2022\tWe perform DFS starting from each cell in the first column, but thanks to memoization, each DFS call explores each cell at most once.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m x n):\n\u2022\tWe use a memo table of size m x n to store the maximum moves from each cell.\n\u2022\tThe DFS call stack has a depth bounded by the grid dimensions, but typically this is optimized away by the memoization\n\n# Code\n```java []\nclass Solution {\n    private int m, n;\n    private int[][] memo;\n    public int maxMoves(int[][] grid) {\n        m = grid.length;\n        n = grid[0].length;\n        memo = new int[m][n];\n        \n        int maxMoves = 0;\n        \n        for (int i = 0; i < m; i++) {\n            maxMoves = Math.max(maxMoves, dfs(grid, i, 0));\n        }\n        \n        return maxMoves;\n    }\n\n    private int dfs(int[][] grid, int row, int col) {\n        if (col == n - 1) return 0;  // last column, no more moves\n        \n        if (memo[row][col] != 0) return memo[row][col];\n        \n        int maxMoves = 0;\n        \n        // Move to the right\n        if (col + 1 < n && grid[row][col + 1] > grid[row][col]) {\n            maxMoves = Math.max(maxMoves, 1 + dfs(grid, row, col + 1));\n        }\n        \n        // Move to the top-right\n        if (row - 1 >= 0 && col + 1 < n && grid[row - 1][col + 1] > grid[row][col]) {\n            maxMoves = Math.max(maxMoves, 1 + dfs(grid, row - 1, col + 1));\n        }\n        \n        // Move to the bottom-right\n        if (row + 1 < m && col + 1 < n && grid[row + 1][col + 1] > grid[row][col]) {\n            maxMoves = Math.max(maxMoves, 1 + dfs(grid, row + 1, col + 1));\n        }\n        \n        memo[row][col] = maxMoves;\n        return maxMoves;\n    }\n}\n```
['Java']