Bottom up DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nWe can initialize a DP 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can initialize a DP array of size ( m X n ) with the first column as 1. \nOne thing to realize is that at any column j if reachable then number of moves would be j. \n\nWith this we can start building up our dp array. I found it easier to conceptualize building this DP array by building a column first and proceeding to the next column. So we will iterate over column first then start iterating over rows. \n\n### Building the DP array\nEverytime we visit a cell in the grid we look into three cells in the preceeding column and check if any of them are less than current value. We should also check if they are reachable. If that is true we will mark the dp cell as non-zero (or j). This DP cell could also be substituted with a boolean array which would indicate whether we can reach that cell by making valid moves.\n\nHopefully this approach is clear, let me know if there are any doubts.\n\n\n# Complexity\n- Time complexity: O(m * n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(m * n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\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        for i in range(m):\n            dp[i][0] = 1\n        res = 0\n        for j in range(1, n):\n            for i in range(m):\n                if i > 0 and grid[i - 1][j - 1] < grid[i][j] and dp[i - 1][j - 1]:\n                    res = max(res, j)\n                    dp[i][j] = j\n                    continue\n                if grid[i][j - 1] < grid[i][j] and dp[i][j - 1]:\n                    res = max(res, j)\n                    dp[i][j] = j\n                    continue\n                if i < m - 1 and grid[i + 1][j - 1] < grid[i][j] and dp[i + 1][j - 1]:\n                    res = max(res, j)\n                    dp[i][j] = j\n                    continue\n        return res\n            \n        \n```\n\n# Space optimized DP\n\n## Complexity\n- Time complexity: O(m * n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(m) [2 * O(m) arrays for storing dp results]\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```\n    def maxMoves(self, grid: list[list[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        prev = [1] * m\n        res = 0\n        for j in range(1, n):\n            cur = [0] * m\n            for i in range(m):\n                if grid[i][j] > grid[i][j - 1] and prev[i]:\n                    cur[i] = j\n                elif i > 0 and grid[i][j] > grid[i - 1][j - 1] and prev[i-1]:\n                    cur[i] = j\n                elif i < m - 1 and grid[i][j] > grid[i + 1][j - 1] and prev[i+1]:\n                    cur[i] = j\n                res = max(res, cur[i])\n            prev = cur\n        return res\n```\n\n
['Python3']