Easy Explanation ✅ !!! Step-by-Step Explanation 🔥🔥 !!! Neat & Clean Code !!! All language 🔥!!!
Approach & Intuition\n1. # Dynamic Programming Table Initialization:\n\n- The DP table dp is initialized with 1\'s, indicating that from each cell, you can at l
# Approach & Intuition\n1. # Dynamic Programming Table Initialization:\n\n- The DP table dp is initialized with 1\'s, indicating that from each cell, you can at least stay in the same cell (which counts as 1 move).\n2. # Backward Iteration:\n\n- The code iterates through the columns from right to left (starting from the second-to-last column).\n- For each cell `(i, j)` in the current column, it considers the possible moves to the cells `(i, j+1)`,` (i+1, j+1)`, and `(i-1, j+1)` if they exist.\n3. # Updating the DP Table:\n\n- For each cell `(i, j)`, it calculates the maximum number of moves that can be made from this cell by considering moves to the right, diagonally up-right, and diagonally down-right.\n- It then updates `dp[i][j]` to be `1 + max_move` where max_move is the maximum number of moves from any of the valid next cells.\n4. # Finding the Result:\n\n- Finally, the code finds the maximum value in the first column of the DP table, as this will represent the maximum number of moves starting from any cell in the first column.\n- The result is adjusted by subtracting 1 because the initial position is not counted as a move according to the problem\'s definition.\n\n# Complexity\n- **Time complexity:**\nThe algorithm consists of two nested loops. The outer loop iterates over the columns of the grid in reverse order (from the second last column to the first column), and the inner loop iterates over the rows of the grid. Since there are \'row\' rows and \'col\' columns, the overall time complexity is `O(row * col)`. This is efficient given that we are processing each cell of the grid once.\n\n- **Space complexity:**\nThe space complexity of the solution is `O(row * col)` due to the additional 2D vector `dp` that is used to store the maximum moves for each cell in the grid. This space is required to keep track of the computed values for each cell, which is necessary for the dynamic programming approach.\n> Keep Hustling !!!!\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        // Get the number of rows and columns in the grid\n        int row = grid.size();\n        int col = grid[0].size();\n\n        // Create a DP table initialized with 1\'s. This table will store the maximum number of moves\n        // we can make starting from each cell.\n        vector<vector<int>> dp(row, vector<int>(col, 1));\n\n        // Iterate through each column starting from the second-to-last column and moving to the first column\n        for (int j = col - 2; j >= 0; j--) {\n            // Iterate through each row\n            for (int i = 0; i < row; i++) {\n                // Get the value of the current cell\n                int val = grid[i][j];\n\n                // Initialize max_move to 0. This will store the maximum moves we can make from this cell.\n                int max_move = val < grid[i][j+1] ? dp[i][j+1] : 0;\n\n                // Check the cell directly below and to the right, if it exists, and update max_move if possible\n                if (i < row - 1) {\n                    max_move = max(max_move, val < grid[i+1][j+1] ? dp[i+1][j+1] : 0);\n                }\n\n                // Check the cell directly above and to the right, if it exists, and update max_move if possible\n                if (i > 0) {\n                    max_move = max(max_move, val < grid[i-1][j+1] ? dp[i-1][j+1] : 0);\n                }\n\n                // Update the DP table for the current cell. The number of moves from this cell is 1\n                // (the move to this cell itself) plus the maximum moves we can make from any of the valid\n                // cells to the right.\n                dp[i][j] = 1 + max_move;\n            }\n        }\n\n        // Find the maximum value in the first column of the DP table, which represents the maximum moves\n        // we can make starting from any cell in the first column.\n        int ans = 0;\n        for (int i = 0; i < row; i++) {\n            ans = max(ans, dp[i][0]);\n        }\n\n        // Return the answer minus 1 because the problem definition considers the starting move as move 0.\n        return ans - 1;\n    }\n};\n```\n```Java []\nimport java.util.*;\n\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int row = grid.length;\n        int col = grid[0].length;\n        int[][] dp = new int[row][col];\n        \n        for (int[] d : dp) {\n            Arrays.fill(d, 1);\n        }\n\n        for (int j = col - 2; j >= 0; j--) {\n            for (int i = 0; i < row; i++) {\n                int val = grid[i][j];\n                int maxMove = val < grid[i][j + 1] ? dp[i][j + 1] : 0;\n\n                if (i < row - 1) {\n                    maxMove = Math.max(maxMove, val < grid[i + 1][j + 1] ? dp[i + 1][j + 1] : 0);\n                }\n\n                if (i > 0) {\n                    maxMove = Math.max(maxMove, val < grid[i - 1][j + 1] ? dp[i - 1][j + 1] : 0);\n                }\n\n                dp[i][j] = 1 + maxMove;\n            }\n        }\n\n        int ans = 0;\n        for (int i = 0; i < row; i++) {\n            ans = Math.max(ans, dp[i][0]);\n        }\n\n        return ans - 1;\n    }\n}\n\n```\n```Python []\nfrom typing import List\n\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        row = len(grid)\n        col = len(grid[0])\n        dp = [[1] * col for _ in range(row)]\n\n        for j in range(col - 2, -1, -1):\n            for i in range(row):\n                val = grid[i][j]\n                max_move = dp[i][j + 1] if val < grid[i][j + 1] else 0\n\n                if i < row - 1:\n                    max_move = max(max_move, dp[i + 1][j + 1] if val < grid[i + 1][j + 1] else 0)\n\n                if i > 0:\n                    max_move = max(max_move, dp[i - 1][j + 1] if val < grid[i - 1][j + 1] else 0)\n\n                dp[i][j] = 1 + max_move\n\n        return max(dp[i][0] for i in range(row)) - 1\n\n```\n```JavaScript []\nfunction maxMoves(grid) {\n    const row = grid.length;\n    const col = grid[0].length;\n    const dp = Array.from({ length: row }, () => Array(col).fill(1));\n\n    for (let j = col - 2; j >= 0; j--) {\n        for (let i = 0; i < row; i++) {\n            const val = grid[i][j];\n            let maxMove = val < grid[i][j + 1] ? dp[i][j + 1] : 0;\n\n            if (i < row - 1) {\n                maxMove = Math.max(maxMove, val < grid[i + 1][j + 1] ? dp[i + 1][j + 1] : 0);\n            }\n\n            if (i > 0) {\n                maxMove = Math.max(maxMove, val < grid[i - 1][j + 1] ? dp[i - 1][j + 1] : 0);\n            }\n\n            dp[i][j] = 1 + maxMove;\n        }\n    }\n\n    let ans = 0;\n    for (let i = 0; i < row; i++) {\n        ans = Math.max(ans, dp[i][0]);\n    }\n\n    return ans - 1;\n}\n```\n```TypeScript []\nfunction maxMoves(grid: number[][]): number {\n    const row = grid.length;\n    const col = grid[0].length;\n    const dp: number[][] = Array.from({ length: row }, () => Array(col).fill(1));\n\n    for (let j = col - 2; j >= 0; j--) {\n        for (let i = 0; i < row; i++) {\n            const val = grid[i][j];\n            let maxMove = val < grid[i][j + 1] ? dp[i][j + 1] : 0;\n\n            if (i < row - 1) {\n                maxMove = Math.max(maxMove, val < grid[i + 1][j + 1] ? dp[i + 1][j + 1] : 0);\n            }\n\n            if (i > 0) {\n                maxMove = Math.max(maxMove, val < grid[i - 1][j + 1] ? dp[i - 1][j + 1] : 0);\n            }\n\n            dp[i][j] = 1 + maxMove;\n        }\n    }\n\n    let ans = 0;\n    for (let i = 0; i < row; i++) {\n        ans = Math.max(ans, dp[i][0]);\n    }\n\n    return ans - 1;\n}\n```
['Array', 'Dynamic Programming', 'Matrix', 'C++', 'Java', 'TypeScript', 'Python3', 'JavaScript']