Example: Fibonacci Number

The standard Fibonacci sequence problem can be solved using tabulation with O(N) space. However, we can optimize it to O(1) using the rolling array concept.

class Fibonacci {
    public static int fibonacciOptimized(int n) {
        if (n <= 1) {
            return n;
        }

        int a = 0;
        int b = 1;
        int sum = 0;

        for (int i = 2; i <= n; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }

        return sum;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci(" + n + ") = " + fibonacciOptimized(n));
    }
}

Explanation: This code keeps track of the two previous Fibonacci numbers (a and b) and calculates the next one (sum) based on them. It doesn't need to store all Fibonacci numbers up to `n`, thus achieving O(1) space complexity.

Example: Minimum Cost Path (2D Grid)

Imagine a 2D grid where each cell has a cost associated with it. You want to find the minimum cost path from the top-left cell to the bottom-right cell, only allowed to move down or right. Standard tabulation uses O(N*M) space. Here's how to optimize it to O(M):

class MinCostPath {
    public static int minCostPathOptimized(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        int[] dp = new int[m];

        for (int i = 0; i < n; i++) {
            int[] temp = new int[m]; // Temporary array to store current row's results
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0) {
                    temp[j] = grid[i][j];
                } else {
                    int up = (i > 0) ? dp[j] : Integer.MAX_VALUE;
                    int left = (j > 0) ? temp[j - 1] : Integer.MAX_VALUE;

                    temp[j] = grid[i][j] + Math.min(up, left);
                }
            }
            dp = temp; // Update the dp array for the next row
        }

        return dp[m - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };

        System.out.println("Minimum Cost Path: " + minCostPathOptimized(grid));
    }
}

Explanation:

• We use `dp` to store the minimum cost to reach each cell in the *previous* row.
• `temp` array is used to calculate the current row's minimum costs, based on the previous row (`dp`) and the current row's left neighbor (`temp[j-1]`).
• After calculating the `temp` array, we update `dp` with the contents of `temp` to prepare for the next row calculation.

This technique reduces space complexity from O(N*M) to O(M), where N is the number of rows and M is the number of columns.

Example: Coin Change (Number of Ways) - Unnecessary Dimension

The coin change problem (finding the number of ways to make change for a given amount) is a classical DP problem. Often implemented using 2D DP, but can be optimized if ordering of coins doesn't matter.

class CoinChange {
    public static int coinChangeOptimized(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // Base case: 1 way to make change for 0 amount

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }

    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
        System.out.println("Number of ways to make change for " + amount + ": " + coinChangeOptimized(amount, coins));
    }
}

Explanation:

• This code uses only a 1D array `dp` to store the number of ways to make change for each amount from 0 to the target `amount`.
• The outer loop iterates through the coins, and the inner loop updates the `dp` array.
• For each coin, the `dp` array is updated in such a way that `dp[i]` stores the number of ways to make change for amount `i` using coins up to the current coin.

This reduces the space complexity from O(amount * coins.length) to O(amount).