JAVA || EASY || 100% || DFS || DP
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the maximum possible moves starting from any cell in the f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the maximum possible moves starting from any cell in the first column, where each move can only go to the next column and to an adjacent row. We aim to explore all possible paths from each cell in the first column, tracking the longest path with an increasing sequence. This can be efficiently achieved using a Depth-First Search (DFS) combined with memoization, which allows us to avoid redundant calculations.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Initialize Variables: Define n (number of columns) and m (number of rows) to easily access grid dimensions. Create an array arr with values {-1, 0, 1} to represent possible row moves (up, stay, down).\n\n- Memoization Table: Create a 2D array t to store the maximum number of moves possible from each cell. Initialize it with -1, indicating uncomputed cells.\n\n- DFS Traversal:\n\n1. For each cell in the first column, initiate a DFS.\n2. In the DFS:\n    If a cell\'s result is already computed (checked in t), \n    return it directly.\n\n    For each possible direction in arr, calculate the new \n    row and move one column to the right. If the new cell\u2019s \n    value is greater than the current cell\u2019s value, recursively \n    call DFS on this new cell and track the maximum moves.\n\n    Store the computed result in the t table for future reference \n    to optimize redundant calculations.\n- Result Calculation: Track the maximum number of moves across all DFS calls initiated from the first column.\n\n- Return Result: After calculating moves from each starting cell in the first column, return the highest count as the answer.\n\n# Complexity\n- Time complexity:O(m * n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(m * n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    int n, m; // col and rows\n    int[] arr = {-1, 0, 1}; // row moving selection\n\n    public int maxMoves(int[][] grid) {\n        n = grid[0].length;\n        m = grid.length;\n\n        int result = 0; // defining the number of moves\n        int[][] t = new int[m][n];\n        \n        // Fill t with -1\n        for (int i = 0; i < m; i++) {\n            Arrays.fill(t[i], -1);\n        }\n\n        for (int row = 0; row < m; row++) {\n            result = Math.max(result, DFS(row, 0, grid, t));\n        }\n\n        return result;\n    }\n\n    private int DFS(int row, int col, int[][] grid, int[][] t) { // dfs to iterate through all the rows with first col only\n        int moves = 0;\n\n        if (t[row][col] != -1) {\n            return t[row][col];\n        }\n\n        for (int dir : arr) {\n            int newRow = row + dir; // new row\n            int newCol = col + 1; // new col\n\n            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] > grid[row][col]) {\n                moves = Math.max(moves, 1 + DFS(newRow, newCol, grid, t)); // checking for the moves in each row\n            }\n        }\n        \n        return t[row][col] = moves;\n    }\n}\n\n```
['Array', 'Dynamic Programming', 'Matrix', 'Java']