🌟 Beats 61.54%  ||  Step-by-Step Breakdown 💯🔥
\n\n## \uD83C\uDF1F Access Daily LeetCode Solutions Repo : click here\n\n---\n\n\n\n---\n\n# Intuition\nThe problem is about finding the longest path in a grid 
![github_promotion_dark.png](https://assets.leetcode.com/users/images/32c5a6d4-fd3e-436c-a8b2-13b2ce31538f_1730162223.4479265.png)\n\n## **\uD83C\uDF1F Access Daily LeetCode Solutions Repo :** [click here](https://github.com/withaarzoo/LeetCode-Solutions)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/c075de6d-b835-48a2-b729-15e356108983_1730162018.7004108.png)\n\n---\n\n# Intuition\nThe problem is about finding the longest path in a grid where you can move only to the right and must always increase in value. The allowed moves make it possible to explore paths either directly right, up-right, or down-right. Given that starting from each cell in the first column might give different paths, we aim to maximize moves by taking advantage of all possible increasing paths.\n\nA key observation is that the problem resembles dynamic programming, where we want to store and build upon solutions for each cell to avoid redundant calculations, especially since the grid size can be large.\n\n---\n\n# Approach\n1. **Dynamic Programming (DP) Setup**: We\'ll use a `dp` table, where `dp[row][col]` holds the maximum number of moves that can be made starting from `grid[row][col]`.\n2. **Reverse DP Calculation**: To avoid recalculations, we\u2019ll populate the DP table from the last column back to the first. This way, each cell\'s result can be built using already-calculated values in the next column.\n3. **Transitions**: For each cell in the grid, check if moving to the right, up-right, or down-right is possible and leads to a strictly greater value. Update the `dp` table based on these moves.\n4. **Result Extraction**: The answer will be the maximum value in the first column of the `dp` table, representing the longest increasing path from any starting cell in the first column.\n\n---\n\n# Complexity\n- **Time complexity**: \\(O(m \\times n)\\), where \\(m\\) and \\(n\\) are the grid dimensions. We examine each cell and compute possible moves in constant time.\n- **Space complexity**: \\(O(m \\times n)\\) for the DP table.\n\n---\n\n# Code\n```C++ []\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        vector<vector<int>> dp(m, vector<int>(n, 0));\n        int maxMoves = 0;\n\n        for (int col = n - 2; col >= 0; --col) {\n            for (int row = 0; row < m; ++row) {\n                if (row > 0 && grid[row][col] < grid[row - 1][col + 1]) {\n                    dp[row][col] = max(dp[row][col], dp[row - 1][col + 1] + 1);\n                }\n                if (grid[row][col] < grid[row][col + 1]) {\n                    dp[row][col] = max(dp[row][col], dp[row][col + 1] + 1);\n                }\n                if (row < m - 1 && grid[row][col] < grid[row + 1][col + 1]) {\n                    dp[row][col] = max(dp[row][col], dp[row + 1][col + 1] + 1);\n                }\n            }\n        }\n\n        for (int row = 0; row < m; ++row) {\n            maxMoves = max(maxMoves, dp[row][0]);\n        }\n        return maxMoves;\n    }\n};\n\n```\n```Java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int m = grid.length, n = grid[0].length;\n        int[][] dp = new int[m][n];\n        int maxMoves = 0;\n\n        for (int col = n - 2; col >= 0; col--) {\n            for (int row = 0; row < m; row++) {\n                if (row > 0 && grid[row][col] < grid[row - 1][col + 1]) {\n                    dp[row][col] = Math.max(dp[row][col], dp[row - 1][col + 1] + 1);\n                }\n                if (grid[row][col] < grid[row][col + 1]) {\n                    dp[row][col] = Math.max(dp[row][col], dp[row][col + 1] + 1);\n                }\n                if (row < m - 1 && grid[row][col] < grid[row + 1][col + 1]) {\n                    dp[row][col] = Math.max(dp[row][col], dp[row + 1][col + 1] + 1);\n                }\n            }\n        }\n\n        for (int row = 0; row < m; row++) {\n            maxMoves = Math.max(maxMoves, dp[row][0]);\n        }\n        return maxMoves;\n    }\n}\n\n```\n```JavaScript []\n/**\n * @param {number[][]} grid\n * @return {number}\n */\nvar maxMoves = function(grid) {\n    const m = grid.length, n = grid[0].length;\n    const dp = Array.from({ length: m }, () => Array(n).fill(0));\n    let maxMoves = 0;\n\n    for (let col = n - 2; col >= 0; col--) {\n        for (let row = 0; row < m; row++) {\n            if (row > 0 && grid[row][col] < grid[row - 1][col + 1]) {\n                dp[row][col] = Math.max(dp[row][col], dp[row - 1][col + 1] + 1);\n            }\n            if (grid[row][col] < grid[row][col + 1]) {\n                dp[row][col] = Math.max(dp[row][col], dp[row][col + 1] + 1);\n            }\n            if (row < m - 1 && grid[row][col] < grid[row + 1][col + 1]) {\n                dp[row][col] = Math.max(dp[row][col], dp[row + 1][col + 1] + 1);\n            }\n        }\n    }\n\n    for (let row = 0; row < m; row++) {\n        maxMoves = Math.max(maxMoves, dp[row][0]);\n    }\n    return maxMoves;\n};\n\n```\n```Python []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        dp = [[0] * n for _ in range(m)]\n        max_moves = 0\n\n        for col in range(n - 2, -1, -1):\n            for row in range(m):\n                if row > 0 and grid[row][col] < grid[row - 1][col + 1]:\n                    dp[row][col] = max(dp[row][col], dp[row - 1][col + 1] + 1)\n                if grid[row][col] < grid[row][col + 1]:\n                    dp[row][col] = max(dp[row][col], dp[row][col + 1] + 1)\n                if row < m - 1 and grid[row][col] < grid[row + 1][col + 1]:\n                    dp[row][col] = max(dp[row][col], dp[row + 1][col + 1] + 1)\n\n        for row in range(m):\n            max_moves = max(max_moves, dp[row][0])\n        return max_moves\n\n```\n```Go []\nfunc maxMoves(grid [][]int) int {\n    m, n := len(grid), len(grid[0])\n    dp := make([][]int, m)\n    for i := range dp {\n        dp[i] = make([]int, n)\n    }\n    maxMoves := 0\n\n    for col := n - 2; col >= 0; col-- {\n        for row := 0; row < m; row++ {\n            if row > 0 && grid[row][col] < grid[row-1][col+1] {\n                dp[row][col] = max(dp[row][col], dp[row-1][col+1]+1)\n            }\n            if grid[row][col] < grid[row][col+1] {\n                dp[row][col] = max(dp[row][col], dp[row][col+1]+1)\n            }\n            if row < m-1 && grid[row][col] < grid[row+1][col+1] {\n                dp[row][col] = max(dp[row][col], dp[row+1][col+1]+1)\n            }\n        }\n    }\n\n    for row := 0; row < m; row++ {\n        maxMoves = max(maxMoves, dp[row][0])\n    }\n    return maxMoves\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n\n```\n---\n\n# Step-by-Step Detailed Explanation\n1. **Initialize DP Table**: We start by creating a DP table `dp` to store the maximum moves from each cell.\n2. **Backwards Traversal**: By processing each column from right to left, each cell\u2019s value is updated based on possible moves to strictly greater values in the next column.\n3. **Calculate Maximum**: Finally, by iterating over the first column, we can determine the maximum number of moves possible by starting from any cell in this column.\n\n---\n\n![upvote_cat.png](https://assets.leetcode.com/users/images/aeaaf7bc-7763-4a3d-8b2c-1b3c10d04111_1730162174.695071.png)\n
['Array', 'Dynamic Programming', 'Matrix', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']