✅ Explained step by step easy to understand | 7ms Beats 90% recursion Dfs with memo✨
Intuition\nThe problem requires finding the maximum moves from the leftmost column to the rightmost column by moving rightward or diagonally right-up or right-d
# Intuition\nThe problem requires finding the maximum moves from the leftmost column to the rightmost column by moving rightward or diagonally right-up or right-down, where each move must go to a cell with a higher value than the current cell. Given the grid structure and movement constraints, a recursive depth-first search (DFS) approach with memoization helps us explore the grid efficiently and prevent recalculations.\n\n![Screenshot 2024-10-30 003008.png](https://assets.leetcode.com/users/images/6328f4a6-8c56-4007-ba01-6bbd9c5b0984_1730228420.2696538.png)\n\n\n# Approach\n1. **Define Valid Moves**: Set three possible moves: rightward, right-up diagonal, and right-down diagonal. This is represented by the directions array.\n2. **Recursive DFS Helper Function**:\n    - The `helper` function calculates the maximum moves possible starting from cell `(i, j)`.\n    - If the value for `(i, j)` is already computed in the t table (memoization array), return it directly to avoid redundant calculations.\n    - For each valid move:\n        - Calculate the new row and column indices.\n        - Check boundary conditions to ensure the move stays within the grid.\n        - Proceed with the move only if the value in the target cell is greater than the current cell value (ensuring increasing order).\n        - Recurse on the new cell, updating the maximum moves from the current cell.\n    - Store the result for `(i, j)` in `t` and return it.\n3. **Initialize Search:**\n    - Iterate over each row of the leftmost column `(j=0)` and invoke `helper` to calculate the maximum moves starting from each cell in this column.\n    - Track the highest number of moves across all possible starting points.\n4. **Memoization Array:** The t array stores intermediate results to avoid repeated calculations, ensuring an efficient solution.\n\n# Complexity\n- Time complexity: **O(m\xD7n)**, where m is the number of rows and n is the number of columns. Each cell is visited only once due to memoization.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(m\xD7n)** for the memoization table t, and O(m\xD7n) for the recursive stack in the worst case.\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> directions = {-1,0,1};\n    int helper(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& t)\n    {\n        if(t[i][j] != -1)\n        {\n            return t[i][j];\n        }\n        int moves = 0;\n        for(int &dir: directions)\n        {\n            int newRow = i+dir;\n            int newCol = j+1;\n\n            if(newRow>=0 && newRow<grid.size() && newCol>=0 && newCol<grid[0].size() && grid[newRow][newCol] > grid[i][j])\n            {\n                moves = max(moves, 1+helper(newRow, newCol, grid, t));\n            }\n        }\n        return t[i][j] = moves;   \n    }\n    int maxMoves(vector<vector<int>>& grid) {\n        int result = 0;\n        vector<vector<int>> t(grid.size(), vector<int>(grid[0].size(), -1));\n        for(int i=0; i<grid.size(); i++)\n        {\n            result = max(result, helper(i,0,grid,t));\n        }\n        return result;\n    }\n};\n```\n``` Java []\nimport java.util.*;\n\nclass Solution {\n    // Directions for moving up, staying at the same row, and moving down\n    private int[] directions = {-1, 0, 1};\n\n    private int helper(int i, int j, int[][] grid, int[][] t) {\n        // If the result is already computed, return it\n        if (t[i][j] != -1) {\n            return t[i][j];\n        }\n        int moves = 0;\n\n        // Iterate through possible directions\n        for (int dir : directions) {\n            int newRow = i + dir;\n            int newCol = j + 1;\n\n            // Check bounds and the condition for moving\n            if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length && grid[newRow][newCol] > grid[i][j]) {\n                moves = Math.max(moves, 1 + helper(newRow, newCol, grid, t));\n            }\n        }\n        return t[i][j] = moves;   \n    }\n\n    public int maxMoves(int[][] grid) {\n        int result = 0;\n        // Create a memoization table initialized to -1\n        int[][] t = new int[grid.length][grid[0].length];\n        for (int i = 0; i < grid.length; i++) {\n            Arrays.fill(t[i], -1); // Fill each row with -1\n        }\n        // Calculate maximum moves for each starting row\n        for (int i = 0; i < grid.length; i++) {\n            result = Math.max(result, helper(i, 0, grid, t));\n        }\n        return result;\n    }\n}\n\n```\n![a-cartoonish-illustration-of-a-hacker-coder-with-a-aNCSswl-SvuAevyOGI5zAA-5eN91EpyQsqInJOcpzklJQ.jpeg](https://assets.leetcode.com/users/images/0fd754fe-8b17-4c5a-8119-a53714dbb434_1730228373.9837508.jpeg)\n
['Array', 'Dynamic Programming', 'Depth-First Search', 'Recursion', 'Matrix', 'C++', 'Java']