Dynamic Programming in Java: Demystifying the 0/1 Knapsack Pattern

Introduction to the 0/1 Knapsack Pattern

Dynamic Programming (DP) is often the most feared topic in coding interviews. It sounds mathematically complex, but at its core, DP is just an optimization over plain recursion. The secret to mastering DP is recognizing patterns, and the 0/1 Knapsack Pattern is the undisputed king of them all.

If you can deeply understand the 0/1 Knapsack problem, you can solve an entire class of DP problems, including Subset Sum, Equal Subset Sum Partition, Minimum Subset Sum Difference, and Count of Subset Sums.

The Core Problem

Imagine you are a thief in a jewelry store. You have a knapsack (a bag) that can hold a maximum weight W. There are N items in the store, each with a specific weight and value. Your goal is to maximize the total value of items you put in your knapsack without exceeding its weight capacity.

The "0/1" Constraint: For every item, you have exactly two choices:

1. Take it (1).
2. Leave it (0). You cannot take fractions of an item (that's the Fractional Knapsack problem, solved with a Greedy approach).

Input:

• weights[] = {1, 2, 3, 5}
• values[] = {1, 6, 10, 16}
• capacity = 7

Step 1: The Brute Force Recursive Approach

The foundation of every DP solution is the recursive relation. To maximize our profit, we need to evaluate all possible combinations of items that fit within the capacity.

For the i-th item, we ask:

• Can it fit in the knapsack? (i.e., weights[i] <= currentCapacity)
  • If Yes, we branch into two universes: one where we include the item, and one where we exclude it. We return the maximum value of these two choices.
  • If No, we have no choice but to exclude it and move to the next item.

class Solution {
    public int solveKnapsack(int[] weights, int[] values, int capacity) {
        return knapsackRecursive(weights, values, capacity, 0);
    }

    private int knapsackRecursive(int[] weights, int[] values, int capacity, int currentIndex) {
        // Base checks: if we run out of capacity or items
        if (capacity <= 0 || currentIndex >= weights.length) {
            return 0;
        }

        // Choice 1: Include the current item (only if it fits)
        int profitWithCurrent = 0;
        if (weights[currentIndex] <= capacity) {
            profitWithCurrent = values[currentIndex] + 
                knapsackRecursive(weights, values, capacity - weights[currentIndex], currentIndex + 1);
        }

        // Choice 2: Exclude the current item
        int profitWithoutCurrent = knapsackRecursive(weights, values, capacity, currentIndex + 1);

        // Return the maximum of both choices
        return Math.max(profitWithCurrent, profitWithoutCurrent);
    }
}

Complexity:

• Time Complexity: $O(2^N)$. For every item, we make two recursive calls. This is an exponential time complexity and will result in a "Time Limit Exceeded" (TLE) error for even moderately sized inputs.
• Space Complexity: $O(N)$. The recursion stack will go as deep as the number of items.

Step 2: Top-Down DP (Memoization)

If you draw out the recursion tree for the brute-force approach, you will notice that we solve the exact same subproblems multiple times. We are repeatedly calculating the max profit for the same capacity and currentIndex.

We can optimize this by storing the result of a subproblem the first time we calculate it. This is called Memoization.

We need a cache. Since our state is defined by two variables (capacity and currentIndex), we need a 2D array: Integer[][] dp = new Integer[weights.length][capacity + 1].

class Solution {
    public int solveKnapsack(int[] weights, int[] values, int capacity) {
        // Use Integer object to distinguish between uninitialized (null) and calculated (0) values
        Integer[][] memo = new Integer[weights.length][capacity + 1];
        return knapsackMemoized(weights, values, capacity, 0, memo);
    }

    private int knapsackMemoized(int[] weights, int[] values, int capacity, int currentIndex, Integer[][] memo) {
        if (capacity <= 0 || currentIndex >= weights.length) return 0;

        // Return cached result if we have already solved this subproblem
        if (memo[currentIndex][capacity] != null) {
            return memo[currentIndex][capacity];
        }

        int profitWithCurrent = 0;
        if (weights[currentIndex] <= capacity) {
            profitWithCurrent = values[currentIndex] + 
                knapsackMemoized(weights, values, capacity - weights[currentIndex], currentIndex + 1, memo);
        }

        int profitWithoutCurrent = knapsackMemoized(weights, values, capacity, currentIndex + 1, memo);

        // Store the result before returning
        memo[currentIndex][capacity] = Math.max(profitWithCurrent, profitWithoutCurrent);
        
        return memo[currentIndex][capacity];
    }
}

Complexity:

• Time Complexity: $O(N \times C)$ where $N$ is the number of items and $C$ is the capacity. We solve each subproblem at most once.
• Space Complexity: $O(N \times C)$ for the memoization array, plus $O(N)$ for the recursion stack.

Step 3: Bottom-Up DP (Tabulation)

Recursion can lead to StackOverflow errors if the input is massive. We can eliminate recursion entirely by building a table from the bottom up.

We build a 2D dp array where dp[i][c] represents the maximum profit we can achieve using the first i items with a knapsack capacity of c.

class Solution {
    public int solveKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        if (capacity <= 0 || n == 0 || weights.length != values.length) return 0;

        int[][] dp = new int[n][capacity + 1];

        // Base case: if we have 0 capacity, profit is 0 (already initialized to 0 in Java)
        
        // Populate the 0th row (considering only the first item)
        for (int c = 0; c <= capacity; c++) {
            if (weights[0] <= c) {
                dp[0][c] = values[0];
            }
        }

        // Process all items for all capacities
        for (int i = 1; i < n; i++) {
            for (int c = 1; c <= capacity; c++) {
                int profitWithCurrent = 0, profitWithoutCurrent = 0;

                // Choice 1: Include the item
                if (weights[i] <= c) {
                    profitWithCurrent = values[i] + dp[i - 1][c - weights[i]];
                }

                // Choice 2: Exclude the item
                profitWithoutCurrent = dp[i - 1][c];

                // Take the max
                dp[i][c] = Math.max(profitWithCurrent, profitWithoutCurrent);
            }
        }

        return dp[n - 1][capacity]; // Result is at the bottom-right corner
    }
}

Complexity:

• Time Complexity: $O(N \times C)$.
• Space Complexity: $O(N \times C)$ for the dp array. No recursion stack overhead.

Step 4: Ultimate Space Optimization

Look closely at the Bottom-Up tabulation loop: dp[i][c] = Math.max(values[i] + dp[i - 1][c - weights[i]], dp[i - 1][c])

Notice that to calculate the values for row i, we only need the values from row i - 1. The rest of the matrix above row i - 1 is completely useless.

We can optimize the space complexity from $O(N \times C)$ to just $O(C)$ by using a single 1D array representing the previous row! We must iterate the inner capacity loop backwards so we don't overwrite values we need for the current calculation.

class Solution {
    public int solveKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        if (capacity <= 0 || n == 0 || weights.length != values.length) return 0;

        // We only need one row of size (capacity + 1)
        int[] dp = new int[capacity + 1];

        // Populate for the 0th item
        for (int c = 0; c <= capacity; c++) {
            if (weights[0] <= c) {
                dp[c] = values[0];
            }
        }

        // Process remaining items
        for (int i = 1; i < n; i++) {
            // Iterate backwards!
            for (int c = capacity; c >= 0; c--) {
                int profitWithCurrent = 0, profitWithoutCurrent = dp[c]; // Exclude is just the old value

                if (weights[i] <= c) {
                    // dp[c - weights[i]] is safely from the previous row because we iterate backwards
                    profitWithCurrent = values[i] + dp[c - weights[i]];
                }

                dp[c] = Math.max(profitWithCurrent, profitWithoutCurrent);
            }
        }

        return dp[capacity];
    }
}

Complexity:

• Time Complexity: $O(N \times C)$.
• Space Complexity: $O(C)$. This is a massive optimization for interviews!

Example 2: Longest Increasing Subsequence (LIS)

Given an integer array nums, return the length of the longest strictly increasing subsequence.

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int maxLen = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

Example 3: Longest Common Subsequence (LCS)

Find the length of the longest common subsequence between two strings.

public int longestCommonSubsequence(String text1, String text2) {
    int[][] dp = new int[text1.length() + 1][text2.length() + 1];
    for (int i = 1; i <= text1.length(); i++) {
        for (int j = 1; j <= text2.length(); j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[text1.length()][text2.length()];
}

Example 4: Coin Change

Find the fewest number of coins that you need to make up an amount.

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Practice Problems for This Pattern

1. 0/1 Knapsack: (Medium)
2. Subset Sum: (Medium)
3. Partition Equal Subset Sum: (Medium)
4. Target Sum: (Medium)
5. Longest Increasing Subsequence: (Medium)
6. Longest Common Subsequence: (Medium)
7. Edit Distance: (Hard)
8. Coin Change: (Medium)
9. Climbing Stairs: (Easy)
10. House Robber: (Medium)

Final Takeaways

• Always start Dynamic Programming problems by defining the recursive brute-force solution. Define your state variables.
• Memoization is just adding a cache to recursion.
• Tabulation removes the recursion stack overhead.
• Space optimization is the final "wow factor" for interviewers, turning a 2D matrix into a 1D array.

Read Next

• DSA in Java Series
• Merge Intervals Pattern in Java
• Tree Traversals in Java