Hop, Skip, Win! Conquer the Grid with Maximum Moves!
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the maximum number of moves starting from any cell in the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the maximum number of moves starting from any cell in the first column of a grid, moving only to adjacent rows in the next column, and ensuring that each move goes to a strictly larger cell value. Given this, a dynamic programming approach is suitable, as we can leverage memoization to avoid redundant calculations and keep track of the maximum moves for each cell.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nRecursive DFS with Memoization: Define a recursive function paths(row, col) that computes the maximum number of moves starting from cell (row, col) in the grid.\n\n\nUse a memoization array dp[prev][ind] to store results for each cell, avoiding recalculations.\nFor each cell, explore moves to the right (ind + 1) in three possible directions: directly to the right, diagonally up-right, and diagonally down-right.\n\n\nIf the target cell\'s value is greater than the current cell, make a recursive call to paths for that cell, accumulating moves.\nBase Case: If we reach the last column, return 0 since no further moves are possible.\n\n\nInitialization: Initialize dp with -1 values, indicating uncomputed cells. Then, iterate over each cell in the first column, calling paths to find the maximum moves starting from each cell.\nResult: The answer is the maximum value returned from paths calls for all cells in the first column.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m\xD7n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m\xD7n)\n\n# Code\n```java []\nclass Solution {\n    int[][] dp;\n    public int paths(int[][] grid, int prev, int ind){\n        if(ind==grid[0].length-1)return 0;\n        if(dp[prev][ind]!=-1) return dp[prev][ind];\n        int max=0;\n        for(int nr: new int[]{prev-1, prev, prev+1}){\n            if(nr>=0 && nr<grid.length) if(grid[nr][ind+1]>grid[prev][ind]){\n                max= Math.max(max, 1+ paths(grid, nr, ind+1));\n            }\n        }\n        return dp[prev][ind]= max;\n    }\n    public int maxMoves(int[][] grid) {\n        int max=0;\n        dp= new int[grid.length][grid[0].length];\n        for(int i=0; i<grid.length; i++) Arrays.fill(dp[i], -1);\n        for(int i=0; i<grid.length; i++){\n            max= Math.max(max, paths(grid, i, 0));\n        }\n        return max;\n    }\n}\n```
['Java']