dp O(m*n) ✅ 7ms, 57MB
\n\n\n# Intuition\nEach cell can be reached by top-left, left and bottom-left if value increasing. We can use an array to store  the maximum moves to reach each
![image.png](https://assets.leetcode.com/users/images/3532aa3d-5a1c-463c-938b-aa1b359e8795_1730211848.2404313.png)\n\n\n# Intuition\nEach cell can be reached by `top-left`, `left` and `bottom-left` if value increasing. We can use an array to store  the maximum moves to reach each row of the current column. \n\nTo save spaces, we don\'t need the whole 2D array, but only O(1) varibale `above` representing `top-left`, together with `dp[i]` and `dp[i+1]` as the three candidates.\n\n# Approach\nInitilize dp and `above` variable, also the final max value.\n```\n        val m = grid.size\n        val n = grid[0].size\n        val dp = IntArray(m)\n        var above = 0 // for rolling storage\n        var max = 0\n```\nA flag for early return. Because if current column is totally not reachable, we can exit and return directly.\n```\n        var allNegative = true\n```\nTraverse each column from index 1, reset early return flag to true:\n```\n        for (col in 1 until n) {\n            allNegative = true\n```\nFor each cell, firstly we store current dp value, which will be next cell\'s `above`:\n```\n            for (row in grid.indices) {\n                val tmp = dp[row] // as "above" for next row\n```\nCalculate the maximum possible moves if it came from:\n- `Above-left`: if it exists, value increasing\n- `Left`: value increasing\n- `Below-left`: if it exists, value increasing\n```\n                var current = -1\n                if (row - 1 >= 0 && above != -1 && grid[row][col] > grid[row - 1][col - 1]) {\n                    current = maxOf(current, above + 1)\n                }\n                if (dp[row] != -1 && grid[row][col] > grid[row][col - 1]) {\n                    current = maxOf(current, dp[row] + 1)\n                }\n                if (row + 1 < m && dp[row + 1] != -1 && grid[row][col] > grid[row + 1][col - 1]) {\n                    current = maxOf(current, dp[row + 1] + 1)\n                }\n```\n\nUpdate `dp[row]` with the best possible moves out of the three.\n```\n                dp[row] = current\n                if (dp[row] != -1) {\n                    allNegative = false // valid path exists\n                }\n```\nprepare next cell\'s `above`\n```\n                // prepare next above\n                above = tmp\n```\nKeep track of the max moves as we fill in each dp[row] for the column.\n```\n                // update max moves\n                max = maxOf(max, dp[row])\n```\nAfter this column\'s iteration, if no valid path, we can exit and return:\n```\n            if (allNegative) return max \n```\notherwise, finish the matrix, return max.\n```\n        return max\n```\n\n# Complexity\n- Time complexity:\n$$O(m * n)$$\n\n- Space complexity:\n$$O(m)$$ due to the rolling dp\n\n# Code\n```kotlin []\nclass Solution {\n    fun maxMoves(grid: Array<IntArray>): Int {\n        val m = grid.size\n        val n = grid[0].size\n        val dp = IntArray(m)\n        var above = 0 // for rolling storage\n        var max = 0\n        var allNegative = true // Flag to check if all dp values are -1\n        for (col in 1 until n) {\n            allNegative = true\n            for (row in grid.indices) {\n                val tmp = dp[row] // as "above" for next row\n                var current = -1\n                if (row - 1 >= 0 && above != -1 && grid[row][col] > grid[row - 1][col - 1]) {\n                    current = maxOf(current, above + 1)\n                }\n                if (dp[row] != -1 && grid[row][col] > grid[row][col - 1]) {\n                    current = maxOf(current, dp[row] + 1)\n                }\n                if (row + 1 < m && dp[row + 1] != -1 && grid[row][col] > grid[row + 1][col - 1]) {\n                    current = maxOf(current, dp[row + 1] + 1)\n                }\n                // update current dp\n                dp[row] = current\n                if (dp[row] != -1) {\n                    allNegative = false // valid path exists\n                }\n                // prepare next above\n                above = tmp\n                // update max moves\n                max = maxOf(max, dp[row])\n            }\n            if (allNegative) return max // if no valid path, we can return\n        }\n\n        return max\n    }\n}\n```
['Array', 'Dynamic Programming', 'Memoization', 'Matrix', 'Kotlin']