[Python3, C++, Java] | Bottom-up DP | O(n) space, O(n * m) time | Optimized space
Intuition\nThe first observation we can come up with is that the result at step n depends only on the result at the step n - 1. Therefore we can conclude that t
# Intuition\nThe first observation we can come up with is that the result at step $$n$$ depends only on the result at the step $$n - 1$$. Therefore we can conclude that there is no point to store steps before $$n - 1$$.\n\nAnother observation is that the number of steps we have taken is always the same as the number of columns where we finished minus 1.\n\n# Approach\nWe iterate in column-first order and for each cell in position $$(r, c)$$ we consider 3 elements from the previous step: $$(r - 1, c - 1)$$, $$(r, c - 1)$$ and $$(r + 1, c - 1)$$.\n\nWe compare the values of elements in such positions considering edge-cases and additionally we check in the $$dp$$-array whether that element was reachable.\n\nIn the end of the internal loop we reassign the $$dp$$ with $$new\\_dp$$ and check whether the $$new\\_dp$$ array still has True values. If no True values are left, it means we cannot move any further and can return the number of steps we have taken so far, which equals $$c - 1$$.\n\n# Complexity\n- Time complexity:\nWe iterate over each element of matrix: $$O(n * m)$$\n\n- Space complexity:\nWe only store reachability of the cells of previous column: $$O(n)$$\n\n# Code\n\n```Python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        n, m = len(grid), len(grid[0])\n        dp = [True] * n\n        for c in range(1, m):\n            new_dp = [False] * n\n            for r in range(n):\n                new_dp[r] |= (grid[r][c - 1] < grid[r][c]) and dp[r]\n                if r > 0:\n                    new_dp[r] |= (grid[r - 1][c - 1] < grid[r][c]) and dp[r - 1]\n                if r < n - 1:\n                    new_dp[r] |= (grid[r + 1][c - 1] < grid[r][c]) and dp[r + 1]\n            if not any(new_dp):\n                return c - 1\n            dp = new_dp\n        return m - 1\n```\n```C++ []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        vector<bool> dp(n, true);\n        \n        for (int c = 1; c < m; ++c) {\n            vector<bool> new_dp(n, false);\n            for (int r = 0; r < n; ++r) {\n                bool flag = false;\n                flag |= (grid[r][c - 1] < grid[r][c]) && dp[r];\n                if (r > 0)\n                    flag |= (grid[r - 1][c - 1] < grid[r][c]) && dp[r - 1];\n\n                if (r < n - 1)\n                    flag |= (grid[r + 1][c - 1] < grid[r][c]) && dp[r + 1];\n                new_dp[r] = flag;\n            }\n\n            if (find(new_dp.begin(), new_dp.end(), true) == new_dp.end())\n                return c - 1;\n\n            dp = new_dp;\n        }\n        return m - 1;\n    }\n};\n\n```\n```Java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int n = grid.length;\n        int m = grid[0].length;\n        boolean[] dp = new boolean[n];\n        Arrays.fill(dp, true);\n\n        for (int c = 1; c < m; ++c) {\n            boolean[] newDp = new boolean[n];\n            boolean movePossible = false;\n            for (int r = 0; r < n; ++r) {\n                newDp[r] |= dp[r] && grid[r][c - 1] < grid[r][c];\n                if (r > 0)\n                    newDp[r] |= dp[r - 1] && grid[r - 1][c - 1] < grid[r][c];\n                if (r < n - 1)\n                    newDp[r] |= dp[r + 1] && grid[r + 1][c - 1] < grid[r][c];\n                movePossible |= newDp[r];\n            }\n \n            if (!movePossible)\n                return c - 1;\n            dp = newDp;\n        }\n\n        return m - 1;\n    }\n}\n\n```\n\n
['Array', 'Dynamic Programming', 'Matrix', 'C++', 'Java', 'Python3']