Maximum Number of Moves in a Grid

This approach optimizes the space complexity of the bottom-up DP solution. By observing the DP state transition, we can see that to compute the values for any column c, we only need the values from the immediately adjacent column c+1. This means we don't need to store the entire 2D DP table. We can use just two 1D arrays (one for the current column, one for the next) to store the necessary information, reducing the space complexity.

• Initialize a 1D array dp of size m with zeros. This array will store the DP values for the column to the right of the one being currently processed.
• Iterate through columns from c = n-2 down to 0.
• Inside the loop, create a new temporary 1D array current_dp of size m to store results for the current column c.
• For each row r from 0 to m-1:
  • Calculate current_dp[r] by checking the three possible moves to column c+1 and using the values from the dp array (which holds values for column c+1).
  • current_dp[r] = max(1 + dp[nr]) over valid moves.
• After iterating through all rows for column c, update dp = current_dp.
• After the main loop finishes, dp will hold the results for the first column. The answer is the maximum value in this dp array.

In the bottom-up DP approach, the calculation of dp[r][c] only depends on dp[...][c+1]. This dependency on only the adjacent column allows for a significant space optimization. Instead of a m x n table, we only need to maintain the DP values for one column at a time.

We can use a 1D array, let's call it dp, of size m, to store the maximum moves from each cell in a given column. We iterate from c = n-2 down to 0. In each iteration, dp holds the values for column c+1. We use another temporary array, current_dp, to compute the values for the current column c. For each row r, current_dp[r] is calculated using the values in dp. After we've computed all values for column c and stored them in current_dp, we update dp = current_dp to prepare for the next iteration (column c-1).

After the loop over all columns is complete, the dp array will contain the maximum moves starting from each cell in the first column. The final answer is the maximum value in this array.

class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[m]; // Represents dp values for the next column (c+1)

        for (int c = n - 2; c >= 0; c--) {
            int[] current_dp = new int[m]; // Represents dp values for the current column c
            for (int r = 0; r < m; r++) {
                // Check move to (r-1, c+1)
                if (r > 0 && grid[r - 1][c + 1] > grid[r][c]) {
                    current_dp[r] = Math.max(current_dp[r], 1 + dp[r - 1]);
                }
                // Check move to (r, c+1)
                if (grid[r][c + 1] > grid[r][c]) {
                    current_dp[r] = Math.max(current_dp[r], 1 + dp[r]);
                }
                // Check move to (r+1, c+1)
                if (r < m - 1 && grid[r + 1][c + 1] > grid[r][c]) {
                    current_dp[r] = Math.max(current_dp[r], 1 + dp[r + 1]);
                }
            }
            dp = current_dp;
        }

        int maxMoves = 0;
        for (int moves : dp) {
            maxMoves = Math.max(maxMoves, moves);
        }

        return maxMoves;
    }
}