Dynamic Programming Interview Lab
Solve classic DP problems using recursion, memoization, and tabulation.
Introduction
30 Second Summary
Imagine someone hands you a pile of coins and asks you to make exact change using the fewest coins possible. You could try every combination, but that would take forever. The trick is recognizing when you are solving the same sub-problem over and over and storing the answer instead of recomputing it.
In this project, you will build a Dynamic Programming laboratory in Java that solves two classic interview problems using progressively optimized approaches. You will see, measure, and internalize why each optimization step matters.
What You'll Build
A set of Java files that implement brute-force recursion, top-down memoization, bottom-up tabulation, and space-optimized solutions for two classic Dynamic Programming interview problems, plus a benchmark suite that proves the performance difference.
By the end of this project, you'll have:
- CoinChange.java with 3 implementations (recursion, memoization, and tabulation) that demonstrate the leap from exponential to polynomial time.
- HouseRobber.java with 4 implementations that take you all the way to O(1) space using rolling variables.
- DPBenchmark.java that runs all approaches side-by-side and prints a timing comparison table so you can see the exponential explosion with your own eyes.
- Secret Mission: extend your framework to 2D DP by solving Minimum Path Sum with all 4 optimization levels.
Are there any prerequisites?
You should be comfortable with Java fundamentals (arrays, recursion, classes) and have a basic understanding of time complexity (Big-O notation). No prior Dynamic Programming experience is needed.
Before We Start
Before We Start...
Set Up Your Project
Before writing any dynamic programming solutions, you need a clean workspace where each Java file compiles and runs independently.
In this step, you will verify your Java installation, create a dedicated project folder on your Desktop, and set up the file structure for your three DP implementation files.
In this step, get ready to:
- Verify JDK 17 is accessible from the command line.
- Create the dp-interview-lab project folder with three Java files.
- Add a compilable class skeleton to CoinChange.java.
Verify your Java environment
Your project needs JDK 17 to compile and run Java files from the terminal. A quick version check confirms everything is accessible.
- Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
- Type VS Code and press Enter to open it.
- Open the integrated terminal by pressing Ctrl+` (backtick key, top-left of keyboard). This works on both macOS and Windows.
- Confirm your Java runtime is available by running this command:
java --versionYou should see output containing 17 in the version number.
- Confirm the Java compiler is available by running:
javac --versionYou should see a version number starting with javac 17.
Not seeing version 17?
If the command prints a version lower than 17, your system may be pointing to an older Java installation. Check that JDK 17 is on your system PATH and takes priority over older versions.
If you see "command not found," JDK 17 is not installed or not on your PATH. Revisit the JDK 17 installation for your operating system before continuing.
Why isn't my Java version showing 17?
Create your project folder and files
You will store all three DP implementation files in a single folder on your Desktop. This keeps everything easy to find and lets you compile files together later.
- Move to your Desktop by running this command:
cd ~/Desktop- Create your project folder and move into it by running these commands:
mkdir dp-interview-lab
cd dp-interview-lab- Now open this folder in VS Code so your workspace is set to the project root.
- Click File in the top menu bar.
- Click Open Folder.
- Navigate to your Desktop, select the dp-interview-lab folder, and click Open.
Why open the folder this way?
Opening a folder as a workspace means VS Code's integrated terminal, file explorer, and search all operate from that folder. Every terminal you open will default to dp-interview-lab as the working directory.
- Open a new terminal in VS Code by pressing Ctrl+`. It should now show dp-interview-lab as the current directory.
- Create the three empty Java files by running this command:
macOS
touch CoinChange.java HouseRobber.java DPBenchmark.javaWindows
New-Item -ItemType "File" -Path "CoinChange.java", "HouseRobber.java", "DPBenchmark.java"- Confirm the files exist by running:
lsYou should see CoinChange.java, HouseRobber.java, and DPBenchmark.java listed in the output.
Don't see all three files?
Make sure your terminal is inside the dp-interview-lab folder. Run pwd (macOS) or cd (Windows) to check your current location.
If you opened a new terminal after opening the folder in VS Code, it should already be in the right place. If not, navigate to the folder again with cd ~/Desktop/dp-interview-lab.
Help me find my project files in the terminal.
Add the class skeleton to CoinChange.java
A Java file needs a class declaration and a main method before it can compile. You will start with a minimal skeleton that verifies your build toolchain works.
- In the VS Code Explorer sidebar on the left, click CoinChange.java to open it.
- Add the following class skeleton:
import java.util.Arrays;
public class CoinChange {
public static void main(String[] args) {
}
}What does this code do?
import java.util.Arrays brings in the Arrays utility class. You will use Arrays.fill() later to initialize memoization arrays with sentinel values.
The main method is the entry point that the JVM calls when you run the file. It is empty for now because you will add DP implementations in the next step.
- Save CoinChange.java by pressing Cmd+S (macOS) or Ctrl+S (Windows).
- Compile the file to verify your skeleton is valid by running:
javac CoinChange.javaIf the command completes with no output, your file compiled successfully. A CoinChange.class file now exists in your folder.
Seeing a compilation error?
Check that your class name CoinChange exactly matches the filename CoinChange.java. Java requires this match to be case-sensitive.
Make sure you saved the file before running javac. Unsaved changes in VS Code will not be picked up by the compiler.
Why won't my CoinChange.java compile?
✔️ Awesome, I've got everything!
Great. Double check you have saved CoinChange.java and that javac CoinChange.java completed with no errors.
ⓧ I'd like to double check the full code
Here is the complete CoinChange.java as it should look at the end of this step:
import java.util.Arrays;
public class CoinChange {
public static void main(String[] args) {
}
}Your project structure is ready. Next up, you will implement three progressively optimized solutions to the Coin Change problem and see firsthand how memoization eliminates exponential blowup.
Implement Coin Change Recursion and Memoization
Your project structure is set up and Java is compiling cleanly. Now it's time to write your first dynamic programming solution.
The Coin Change problem asks: given a set of coin denominations, what's the fewest coins needed to make a target amount? You'll solve it first with brute-force recursion, then add memoization to eliminate redundant work. By the end, you'll see the exponential-to-polynomial improvement with your own eyes.
In this step, get ready to:
- Implement a brute-force recursive Coin Change solution.
- Add top-down memoization to cache subproblem results.
- Run both approaches with timing to observe the performance gap.
Write the brute-force recursive solution
The recursive approach models the problem naturally. At each step, you try every coin denomination: subtract it from the remaining amount and recurse. The base cases are straightforward: amount equals 0 means you found a valid combination (return 0 coins), and amount less than 0 means this path is invalid (return -1).
- In CoinChange.java, add the following method above the main method (between the opening class brace and public static void main):
// Approach 1: Brute Force Recursion
// Time: O(k^amount) where k = number of coins
// Space: O(amount) for recursion stack
public static int coinChangeRecursive(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeRecursive(coins, amount - coin);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}What does this code do?
This method tries every possible coin at each step and picks the path that uses the fewest total coins.
- if (amount == 0) return 0 is the success base case. You've made exact change with zero additional coins.
- if (amount < 0) return -1 means this coin combination overshoots the target.
- The loop tries subtracting each coin and recursing. It keeps the minimum result across all choices.
- If no valid combination exists, the method returns -1.
You won't see output yet. The next chunks build the memoized version and the main method that runs everything together.
Add memoization to eliminate redundant computation
The recursive solution recalculates the same subproblems many times. For example, coinChangeRecursive(coins, 30) gets called from multiple different paths in the recursion tree. Memoization stores each result the first time it's computed, so future calls return instantly from the cache.
- Add the following two methods below coinChangeRecursive and above main:
// Approach 2: Top-Down Memoization
// Time: O(amount * coins.length)
// Space: O(amount) for memo array + O(amount) for recursion stack
public static int coinChangeMemo(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2);
return coinChangeMemoHelper(coins, amount, memo);
}
private static int coinChangeMemoHelper(int[] coins, int amount, int[] memo) {
if (amount == 0) return 0;
if (amount < 0) return -1;
if (memo[amount] != -2) return memo[amount];
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeMemoHelper(coins, amount - coin, memo);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
memo[amount] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
return memo[amount];
}What does this code do?
The memoized version uses the same recursive logic but caches every computed result in an array.
- int[] memo = new int[amount + 1] creates the cache. Each index stores the answer for that subproblem amount.
- Arrays.fill(memo, -2) initializes with -2 as a sentinel meaning "not computed yet". You can't use -1 because that's already a valid return value (meaning "impossible").
- if (memo[amount] != -2) return memo[amount] is the cache hit. If this subproblem was solved before, return immediately.
- After computing the result, it's stored in memo[amount] before returning. Every future call with the same amount skips all the recursion.
Why -2 as a sentinel instead of -1?
In the Coin Change problem, -1 is a legitimate answer meaning "this amount is impossible to make with these coins." If you used -1 as your "not computed" marker, you couldn't distinguish between "I haven't tried this yet" and "I tried and it's impossible." Using -2 avoids this ambiguity.
You won't see output yet. The next chunk builds the main method that calls both approaches and prints timing.
Run both approaches and observe the performance gap
Now you'll build a main method that runs both solutions on the same input and measures how long each takes. You'll also run the memoized version on a larger input (amount = 100) where recursion would take hours.
- Replace the empty main method in CoinChange.java with this code:
public static void main(String[] args) {
int[] coins = {1, 5, 10, 25};
int amount = 36;
System.out.println("=== Coin Change Problem ===");
System.out.println("Coins: " + Arrays.toString(coins));
System.out.println("Amount: " + amount);
System.out.println();
System.out.println("Approach 1: Brute Force Recursion");
long start = System.nanoTime();
int result1 = coinChangeRecursive(coins, amount);
long end = System.nanoTime();
System.out.println("Result: " + result1 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 2: Top-Down Memoization");
start = System.nanoTime();
int result2 = coinChangeMemo(coins, amount);
end = System.nanoTime();
System.out.println("Result: " + result2 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("=== Exponential Explosion Demo ===");
int largeAmount = 100;
System.out.println("Amount = " + largeAmount + " (recursion would take hours!)");
start = System.nanoTime();
int result4 = coinChangeMemo(coins, largeAmount);
end = System.nanoTime();
System.out.println("Memoization: " + result4 + " coins, Time: " + (end - start) / 1_000_000.0 + " ms");
}What does this code do?
The main method acts as your benchmark harness, running both implementations on the same inputs and printing timing data.
- System.nanoTime() captures high-resolution timestamps before and after each call. The difference, divided by 1,000,000, gives milliseconds.
- The test uses coins [1, 5, 10, 25] with amount 36. The optimal answer is 3 coins (25 + 10 + 1).
- The "Exponential Explosion Demo" section runs only memoization on amount = 100. Running recursion on this input would take hours due to exponential branching.
- Save CoinChange.java.
- Compile and run the file by running these commands in your terminal:
javac CoinChange.java
java CoinChange- You should see output showing both approaches returning 3 coins for amount 36. The recursion time will be noticeably larger than memoization. The large-input demo (amount = 100) should complete in under 1 ms with memoization.
Seeing a compilation error?
- Check that import java.util.Arrays; is at the very top of the file. Without it, Arrays.fill and Arrays.toString won't resolve.
- Make sure the methods are inside the CoinChange class braces but outside the main method braces. Methods cannot be nested inside other methods in Java.
- Verify you don't have two main methods. You should have replaced the empty one, not added a second.
Still stuck? Help me fix a compilation error in my CoinChange.java file
✔️ Awesome, I've got everything!
Great. Make sure you've saved CoinChange.java and that both approaches return 3 for amount 36.
ⓧ I'd like to double check the full code
Here's the complete CoinChange.java at this point:
import java.util.Arrays;
public class CoinChange {
// Approach 1: Brute Force Recursion
// Time: O(k^amount) where k = number of coins
// Space: O(amount) for recursion stack
public static int coinChangeRecursive(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeRecursive(coins, amount - coin);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}
// Approach 2: Top-Down Memoization
// Time: O(amount * coins.length)
// Space: O(amount) for memo array + O(amount) for recursion stack
public static int coinChangeMemo(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2);
return coinChangeMemoHelper(coins, amount, memo);
}
private static int coinChangeMemoHelper(int[] coins, int amount, int[] memo) {
if (amount == 0) return 0;
if (amount < 0) return -1;
if (memo[amount] != -2) return memo[amount];
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeMemoHelper(coins, amount - coin, memo);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
memo[amount] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
return memo[amount];
}
public static void main(String[] args) {
int[] coins = {1, 5, 10, 25};
int amount = 36;
System.out.println("=== Coin Change Problem ===");
System.out.println("Coins: " + Arrays.toString(coins));
System.out.println("Amount: " + amount);
System.out.println();
System.out.println("Approach 1: Brute Force Recursion");
long start = System.nanoTime();
int result1 = coinChangeRecursive(coins, amount);
long end = System.nanoTime();
System.out.println("Result: " + result1 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 2: Top-Down Memoization");
start = System.nanoTime();
int result2 = coinChangeMemo(coins, amount);
end = System.nanoTime();
System.out.println("Result: " + result2 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("=== Exponential Explosion Demo ===");
int largeAmount = 100;
System.out.println("Amount = " + largeAmount + " (recursion would take hours!)");
start = System.nanoTime();
int result4 = coinChangeMemo(coins, largeAmount);
end = System.nanoTime();
System.out.println("Memoization: " + result4 + " coins, Time: " + (end - start) / 1_000_000.0 + " ms");
}
}You've now seen the core DP insight firsthand: the same recursive logic goes from unusable to instant just by caching results. Next up, you'll convert this top-down approach into bottom-up tabulation, eliminating the recursion stack entirely.
Add Coin Change Tabulation
Your memoization solution already brings Coin Change from exponential to polynomial time. The next question interviewers ask is: can you eliminate the recursion stack entirely?
Bottom-up tabulation flips the approach. Instead of starting at the target and recursing down, you start at 0 and build up. This eliminates the recursion stack, avoids StackOverflowError on large inputs, and gives the JVM predictable memory access patterns.
In this step, get ready to:
- Implement a bottom-up tabulation method for Coin Change.
- Update the main method to benchmark all three approaches side by side.
- Understand why tabulation is preferred over memoization for this problem.
Convert memoization to bottom-up tabulation
Tabulation works by building a table from the smallest subproblem (amount = 0) up to the target. For each amount from 1 to the target, you try every coin and keep the minimum.
- In CoinChange.java, find the closing brace } of the coinChangeMemoHelper method.
- Add the following tabulation method below it:
// Approach 3: Bottom-Up Tabulation
// Time: O(amount * coins.length)
// Space: O(amount)
public static int coinChangeTabulation(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 (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}What does this code do?
This method builds an array dp where dp[i] holds the minimum coins needed for amount i.
- Arrays.fill(dp, amount + 1) initializes every cell to a value larger than any valid answer. This acts as "infinity" so Math.min comparisons work correctly.
- dp[0] = 0 is the base case: zero coins needed to make amount 0.
- The nested loop tries each coin at each amount. If using that coin gives a smaller result, the cell updates.
- The final check dp[amount] > amount detects impossible cases (the value never got updated from "infinity").
- Save CoinChange.java.
- Compile to check for syntax errors by running:
javac CoinChange.java- You should see no output, meaning the file compiled successfully.
Seeing a compilation error?
- Make sure the method is placed between the closing brace of coinChangeMemoHelper and the main method. It must be inside the CoinChange class.
- Check that you have the import java.util.Arrays; line at the top of the file.
Help me fix my coinChangeTabulation compilation error
Update main to benchmark all three approaches
Your main method currently runs recursion and memoization. You need to add tabulation to both the regular benchmark and the large-input demo.
- In the main method, find this line:
System.out.println("=== Exponential Explosion Demo ===");- Add the following tabulation timing block directly above that line:
System.out.println("Approach 3: Bottom-Up Tabulation");
start = System.nanoTime();
int result3 = coinChangeTabulation(coins, amount);
end = System.nanoTime();
System.out.println("Result: " + result3 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();What does this code do?
This follows the same timing pattern as the recursion and memoization blocks above it. It wraps the tabulation call in System.nanoTime() measurements so you can compare execution speed across all three approaches.
- Now scroll to the very end of the main method. Find this line (the last print statement):
System.out.println("Memoization: " + result4 + " coins, Time: " + (end - start) / 1_000_000.0 + " ms");- Add the tabulation large-input benchmark directly below it:
start = System.nanoTime();
int result5 = coinChangeTabulation(coins, largeAmount);
end = System.nanoTime();
System.out.println("Tabulation: " + result5 + " coins, Time: " + (end - start) / 1_000_000.0 + " ms");Why skip recursion for the large input?
The recursive approach has O(k^amount) time complexity. For amount = 100, that means trillions of function calls. It would take hours or hang indefinitely. Memoization and tabulation both run in O(amount * coins.length), finishing instantly.
- Save CoinChange.java.
- Compile and run the program by running these commands:
javac CoinChange.java
java CoinChange- You should see all three approaches return 3 coins for amount = 36 (25 + 10 + 1). The Exponential Explosion Demo should show both memoization and tabulation returning 4 coins for amount = 100 with sub-millisecond times.
Getting different results across approaches?
- If tabulation returns a different number, check that dp[0] = 0 is set after Arrays.fill. If you set it before, the fill overwrites it.
- Make sure the inner loop condition is coin <= i (not coin < i). Missing the equals sign skips exact-change cases.
Help me debug my tabulation results
✔️ Awesome, I've got everything!
Great. Double check you have saved CoinChange.java and all three approaches return the same results.
ⓧ I'd like to double check the full code
Here is the complete CoinChange.java at this point:
import java.util.Arrays;
public class CoinChange {
// Approach 1: Brute Force Recursion
// Time: O(k^amount) where k = number of coins
// Space: O(amount) for recursion stack
public static int coinChangeRecursive(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeRecursive(coins, amount - coin);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}
// Approach 2: Top-Down Memoization
// Time: O(amount * coins.length)
// Space: O(amount) for memo array + O(amount) for recursion stack
public static int coinChangeMemo(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2);
return coinChangeMemoHelper(coins, amount, memo);
}
private static int coinChangeMemoHelper(int[] coins, int amount, int[] memo) {
if (amount == 0) return 0;
if (amount < 0) return -1;
if (memo[amount] != -2) return memo[amount];
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeMemoHelper(coins, amount - coin, memo);
if (result != -1) {
minCoins = Math.min(minCoins, result + 1);
}
}
memo[amount] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
return memo[amount];
}
// Approach 3: Bottom-Up Tabulation
// Time: O(amount * coins.length)
// Space: O(amount)
public static int coinChangeTabulation(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 (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] coins = {1, 5, 10, 25};
int amount = 36;
System.out.println("=== Coin Change Problem ===");
System.out.println("Coins: " + Arrays.toString(coins));
System.out.println("Amount: " + amount);
System.out.println();
System.out.println("Approach 1: Brute Force Recursion");
long start = System.nanoTime();
int result1 = coinChangeRecursive(coins, amount);
long end = System.nanoTime();
System.out.println("Result: " + result1 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 2: Top-Down Memoization");
start = System.nanoTime();
int result2 = coinChangeMemo(coins, amount);
end = System.nanoTime();
System.out.println("Result: " + result2 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 3: Bottom-Up Tabulation");
start = System.nanoTime();
int result3 = coinChangeTabulation(coins, amount);
end = System.nanoTime();
System.out.println("Result: " + result3 + " coins");
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("=== Exponential Explosion Demo ===");
int largeAmount = 100;
System.out.println("Amount = " + largeAmount + " (recursion would take hours!)");
start = System.nanoTime();
int result4 = coinChangeMemo(coins, largeAmount);
end = System.nanoTime();
System.out.println("Memoization: " + result4 + " coins, Time: " + (end - start) / 1_000_000.0 + " ms");
start = System.nanoTime();
int result5 = coinChangeTabulation(coins, largeAmount);
end = System.nanoTime();
System.out.println("Tabulation: " + result5 + " coins, Time: " + (end - start) / 1_000_000.0 + " ms");
}
}Understand why tabulation is preferred here
Both memoization and tabulation have the same O(amount * coins.length) time complexity. So why would an interviewer ask you to convert?
Why tabulation over memoization?
- No recursion stack overhead. Memoization still recurses, meaning each call adds a frame to the stack. For very large amounts, this causes a StackOverflowError. Tabulation uses a simple loop.
- Predictable memory access. Tabulation fills the array sequentially from index 0 to the target. This is cache-friendly. Memoization jumps around the array based on recursion order.
- Interview signal. Offering to convert from top-down to bottom-up shows you understand both approaches and can choose the right one for the constraint.
Interview strategy for Coin Change
Start with memoization (faster to write under pressure and mirrors the recursive structure). Then offer bottom-up tabulation as an optimization. Mentioning the stack overflow risk for large inputs demonstrates senior-level awareness.
You now have all three optimization levels for Coin Change: brute force, memoization, and tabulation. Next up, you will apply the full 4-step DP framework to a new problem pattern and add space optimization on top.
Build House Robber with All Four Approaches
Your Coin Change solutions proved how memoization and tabulation collapse exponential runtimes into polynomial ones.
Now you will tackle a second DP pattern: the House Robber problem. Given an array of house values, you need to find the maximum loot you can steal without robbing two adjacent houses. This is the Linear DP pattern, where each state depends only on a fixed window of previous states. That constant window is what unlocks the fourth optimization level: replacing the entire DP array with just two variables.
In this step, get ready to:
- Write brute-force recursion and memoization for the House Robber problem.
- Convert to bottom-up tabulation and apply space optimization with rolling variables.
- Run all four approaches and benchmark recursion against the optimized version on a larger input.
Write recursion and memoization
The House Robber recurrence has a simple structure. At each house i, you either skip it (take the best loot from houses 0 to i-1) or rob it (take the best loot from houses 0 to i-2 plus the current house value).
- Open HouseRobber.java in VS Code and add the import, class declaration, brute-force recursion, and memoization by pasting this code:
import java.util.Arrays;
public class HouseRobber {
// Approach 1: Brute Force Recursion
// Time: O(2^n)
// Space: O(n) for recursion stack
public static int robRecursive(int[] nums) {
return robRecursiveHelper(nums, nums.length - 1);
}
private static int robRecursiveHelper(int[] nums, int i) {
if (i < 0) return 0;
return Math.max(
robRecursiveHelper(nums, i - 1),
robRecursiveHelper(nums, i - 2) + nums[i]
);
}
// Approach 2: Top-Down Memoization
// Time: O(n)
// Space: O(n) for memo + O(n) for recursion stack
public static int robMemo(int[] nums) {
int[] memo = new int[nums.length];
Arrays.fill(memo, -1);
return robMemoHelper(nums, nums.length - 1, memo);
}
private static int robMemoHelper(int[] nums, int i, int[] memo) {
if (i < 0) return 0;
if (memo[i] != -1) return memo[i];
memo[i] = Math.max(
robMemoHelper(nums, i - 1, memo),
robMemoHelper(nums, i - 2, memo) + nums[i]
);
return memo[i];
}What does this code do?
These are the first two approaches of your 4-step framework applied to a new problem.
- robRecursiveHelper starts at the last house and branches two ways at every index: skip or rob. This creates an O(2^n) recursion tree with massive overlap.
- robMemoHelper uses -1 as a sentinel because all house values are positive, so the real answer is always >= 0. Once a subproblem is solved, it never recomputes.
Why -1 here but -2 for Coin Change?
Coin Change uses -2 as its sentinel because -1 is already a valid return value (meaning "impossible"). House Robber's answer is always non-negative, so -1 works fine as "not yet computed."
You will not see a change yet. The next chunk adds tabulation and space optimization to complete the file.
Convert to tabulation and space optimization
The tabulation version fills a dp[] array from left to right. Since each cell only looks back two positions, you can replace the entire array with just two rolling variables.
- In HouseRobber.java, add the tabulation and space-optimized methods directly below the memoization code:
// Approach 3: Bottom-Up Tabulation
// Time: O(n)
// Space: O(n)
public static int robTabulation(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
// Approach 4: Space-Optimized
// Time: O(n)
// Space: O(1)
public static int robOptimized(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int prevTwo = nums[0];
int prevOne = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int current = Math.max(prevOne, prevTwo + nums[i]);
prevTwo = prevOne;
prevOne = current;
}
return prevOne;
}What does this code do?
- robTabulation fills an array iteratively. dp[0] is the first house value, dp[1] is the better of house 0 or house 1, then each subsequent cell picks the max of skipping or robbing.
- robOptimized replaces the entire array with two variables: prevTwo (the answer two positions back) and prevOne (the answer one position back). This drops space from O(n) to O(1).
Watch the variable order
In the space-optimized version, compute current BEFORE shifting prevTwo and prevOne. If you overwrite prevTwo first, you lose the value you need for the calculation. This is a common bug in interviews.
You will not see a change yet. The next chunk adds the main method that runs and times all four approaches.
Build the main method and run all four approaches
The main method will run all four approaches on the test array [2, 7, 9, 3, 1, 5, 8, 4], print results and timing, then scale up to 30 houses to show how recursion collapses under load.
- Add the main method and closing brace below the robOptimized method:
public static void main(String[] args) {
int[] houses = {2, 7, 9, 3, 1, 5, 8, 4};
System.out.println("=== House Robber Problem ===");
System.out.println("Houses: " + Arrays.toString(houses));
System.out.println();
System.out.println("Approach 1: Brute Force Recursion");
long start = System.nanoTime();
int result1 = robRecursive(houses);
long end = System.nanoTime();
System.out.println("Max loot: $" + result1);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 2: Top-Down Memoization");
start = System.nanoTime();
int result2 = robMemo(houses);
end = System.nanoTime();
System.out.println("Max loot: $" + result2);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 3: Bottom-Up Tabulation");
start = System.nanoTime();
int result3 = robTabulation(houses);
end = System.nanoTime();
System.out.println("Max loot: $" + result3);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 4: Space-Optimized (O(1) space)");
start = System.nanoTime();
int result4 = robOptimized(houses);
end = System.nanoTime();
System.out.println("Max loot: $" + result4);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("=== Scaling Demo ===");
int[] largeHouses = new int[30];
for (int i = 0; i < 30; i++) {
largeHouses[i] = (i * 7 + 3) % 20 + 1;
}
System.out.println("30 houses - recursion slows dramatically:");
start = System.nanoTime();
int resultLarge1 = robRecursive(largeHouses);
end = System.nanoTime();
System.out.println("Recursion: $" + resultLarge1 + ", Time: " + (end - start) / 1_000_000.0 + " ms");
start = System.nanoTime();
int resultLarge2 = robOptimized(largeHouses);
end = System.nanoTime();
System.out.println("Optimized: $" + resultLarge2 + ", Time: " + (end - start) / 1_000_000.0 + " ms");
}
}What does this code do?
- The first section runs all four approaches on the 8-house test array and prints both the result and the execution time using System.nanoTime().
- The scaling demo generates a 30-element array and pits brute-force recursion against the space-optimized version. With 30 houses, the O(2^n) recursion explores over a billion paths while the optimized version loops 28 times.
- Save HouseRobber.java.
- Compile the file by running this command in your terminal:
javac HouseRobber.java- Run the program by executing:
java HouseRobber- You should see all four approaches return Max loot: $20 for the test array. In the scaling demo, recursion should take noticeably longer (hundreds of milliseconds or more) while the optimized version finishes in microseconds.
Why is the scaling demo so dramatic?
With 30 houses, the recursive version makes roughly 2^30 (over one billion) calls. The space-optimized version makes exactly 28 iterations through a simple loop. This is the difference between O(2^n) and O(n) in a way you can feel in the execution time.
Not seeing $20 for all four approaches?
- Check that robRecursiveHelper uses nums.length - 1 as its starting index (not nums.length).
- In robOptimized, verify that current is computed before prevTwo = prevOne. Swapping the order gives wrong results.
- Make sure robTabulation sets dp[1] = Math.max(nums[0], nums[1]), not just nums[1]. You need the best answer for the first two houses, not just the second house value.
Help me debug my House Robber implementation. All four approaches should return 20 but I'm getting a different answer.
✔️ Awesome, I've got everything!
Great. Double check you have saved HouseRobber.java and all four results show $20.
ⓧ I'd like to double check the full code
Here is the complete HouseRobber.java for comparison:
import java.util.Arrays;
public class HouseRobber {
// Approach 1: Brute Force Recursion
// Time: O(2^n)
// Space: O(n) for recursion stack
public static int robRecursive(int[] nums) {
return robRecursiveHelper(nums, nums.length - 1);
}
private static int robRecursiveHelper(int[] nums, int i) {
if (i < 0) return 0;
return Math.max(
robRecursiveHelper(nums, i - 1),
robRecursiveHelper(nums, i - 2) + nums[i]
);
}
// Approach 2: Top-Down Memoization
// Time: O(n)
// Space: O(n) for memo + O(n) for recursion stack
public static int robMemo(int[] nums) {
int[] memo = new int[nums.length];
Arrays.fill(memo, -1);
return robMemoHelper(nums, nums.length - 1, memo);
}
private static int robMemoHelper(int[] nums, int i, int[] memo) {
if (i < 0) return 0;
if (memo[i] != -1) return memo[i];
memo[i] = Math.max(
robMemoHelper(nums, i - 1, memo),
robMemoHelper(nums, i - 2, memo) + nums[i]
);
return memo[i];
}
// Approach 3: Bottom-Up Tabulation
// Time: O(n)
// Space: O(n)
public static int robTabulation(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
// Approach 4: Space-Optimized
// Time: O(n)
// Space: O(1)
public static int robOptimized(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int prevTwo = nums[0];
int prevOne = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int current = Math.max(prevOne, prevTwo + nums[i]);
prevTwo = prevOne;
prevOne = current;
}
return prevOne;
}
public static void main(String[] args) {
int[] houses = {2, 7, 9, 3, 1, 5, 8, 4};
System.out.println("=== House Robber Problem ===");
System.out.println("Houses: " + Arrays.toString(houses));
System.out.println();
System.out.println("Approach 1: Brute Force Recursion");
long start = System.nanoTime();
int result1 = robRecursive(houses);
long end = System.nanoTime();
System.out.println("Max loot: $" + result1);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 2: Top-Down Memoization");
start = System.nanoTime();
int result2 = robMemo(houses);
end = System.nanoTime();
System.out.println("Max loot: $" + result2);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 3: Bottom-Up Tabulation");
start = System.nanoTime();
int result3 = robTabulation(houses);
end = System.nanoTime();
System.out.println("Max loot: $" + result3);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("Approach 4: Space-Optimized (O(1) space)");
start = System.nanoTime();
int result4 = robOptimized(houses);
end = System.nanoTime();
System.out.println("Max loot: $" + result4);
System.out.println("Time: " + (end - start) / 1_000_000.0 + " ms");
System.out.println();
System.out.println("=== Scaling Demo ===");
int[] largeHouses = new int[30];
for (int i = 0; i < 30; i++) {
largeHouses[i] = (i * 7 + 3) % 20 + 1;
}
System.out.println("30 houses - recursion slows dramatically:");
start = System.nanoTime();
int resultLarge1 = robRecursive(largeHouses);
end = System.nanoTime();
System.out.println("Recursion: $" + resultLarge1 + ", Time: " + (end - start) / 1_000_000.0 + " ms");
start = System.nanoTime();
int resultLarge2 = robOptimized(largeHouses);
end = System.nanoTime();
System.out.println("Optimized: $" + resultLarge2 + ", Time: " + (end - start) / 1_000_000.0 + " ms");
}
}Why is this the "rolling variables" pattern?
Interviewers often ask a follow-up: "Can you optimize the space?" Whenever a DP recurrence depends on a fixed-size window of previous states (here just 2), you can replace the full array with that many variables. The variables "roll forward" as you iterate, carrying only what the next computation needs.
Coin Change cannot use this trick because dp[i] depends on dp[i - coin] for every coin denomination. The window is not constant. That is why having two different problem patterns in your lab matters.
You now have two complete DP problem solutions with different patterns. Next up, you will wire both into a benchmark suite that visualizes performance across multiple input sizes.
Build the Benchmark Suite
You now have two complete DP solutions: Coin Change and House Robber. Each file runs its own timing demo, but comparing across approaches and input sizes requires switching between outputs.
In this step, you will build a dedicated benchmark file that calls every implementation from both problems, formats the results into a clean comparison table, and surfaces the key insight: recursion explodes while optimized approaches stay fast.
In this step, get ready to:
- Build a benchmark suite that calls methods from both solution files.
- Create formatted comparison tables across multiple input sizes.
- Compile and run all three files together to observe performance differences.
Build the benchmark file with the Coin Change comparison
The benchmark file ties everything together. It calls the public static methods from CoinChange and HouseRobber directly, times each approach, and prints the results in a table.
- In VS Code, open DPBenchmark.java (the empty file you created in Step 1).
- Add the class skeleton with the main method and two utility helpers by pasting this code:
public class DPBenchmark {
public static void main(String[] args) {
System.out.println("==================================================");
System.out.println(" Dynamic Programming Benchmark Suite ");
System.out.println("==================================================");
System.out.println();
benchmarkCoinChange();
System.out.println();
benchmarkHouseRobber();
}
private static int[] generateHouses(int n) {
int[] houses = new int[n];
for (int i = 0; i < n; i++) {
houses[i] = (i * 7 + 3) % 20 + 1;
}
return houses;
}
private static String formatTime(long nanos) {
if (nanos < 1_000) {
return nanos + " ns";
} else if (nanos < 1_000_000) {
return String.format("%.1f us", nanos / 1_000.0);
} else if (nanos < 1_000_000_000) {
return String.format("%.2f ms", nanos / 1_000_000.0);
} else {
return String.format("%.2f s", nanos / 1_000_000_000.0);
}
}
}What does this code do?
The main method prints a header banner and then calls two benchmark methods (which you will add next).
The generateHouses helper creates a deterministic array of house values using a formula. This ensures every run produces the same numbers so timings are comparable.
The formatTime helper converts raw nanoseconds into human-readable units (ns, us, ms, or s) depending on magnitude.
- Save DPBenchmark.java.
Now add the Coin Change benchmark method. This method tests all three Coin Change approaches across multiple input sizes and displays a formatted table.
- In DPBenchmark.java, add the benchmarkCoinChange method above the generateHouses method:
private static void benchmarkCoinChange() {
System.out.println("=== COIN CHANGE BENCHMARK ===");
System.out.println("Coins: [1, 5, 10, 25]");
System.out.println();
int[] coins = {1, 5, 10, 25};
int[] testAmounts = {10, 20, 30, 36, 50};
System.out.printf("%-8s | %-15s | %-15s | %-15s%n",
"Amount", "Recursion", "Memoization", "Tabulation");
System.out.println("-".repeat(62));
for (int amount : testAmounts) {
long start = System.nanoTime();
CoinChange.coinChangeRecursive(coins, amount);
long recursionTime = System.nanoTime() - start;
start = System.nanoTime();
CoinChange.coinChangeMemo(coins, amount);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
CoinChange.coinChangeTabulation(coins, amount);
long tabTime = System.nanoTime() - start;
System.out.printf("%-8d | %-15s | %-15s | %-15s%n",
amount,
formatTime(recursionTime),
formatTime(memoTime),
formatTime(tabTime));
}
System.out.println();
System.out.println("Large input (amount = 200) - Recursion skipped (too slow):");
int largeAmount = 200;
long start = System.nanoTime();
int r2 = CoinChange.coinChangeMemo(coins, largeAmount);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
int r3 = CoinChange.coinChangeTabulation(coins, largeAmount);
long tabTime = System.nanoTime() - start;
System.out.printf(" Memoization: %d coins in %s%n", r2, formatTime(memoTime));
System.out.printf(" Tabulation: %d coins in %s%n", r3, formatTime(tabTime));
}What does this code do?
The method loops over test amounts [10, 20, 30, 36, 50] and times each of the three Coin Change approaches. It prints results in a formatted table using printf for aligned columns.
For the large-input demo (amount = 200), recursion is intentionally skipped because it would take an impractical amount of time. Only memoization and tabulation run at that scale.
- Save DPBenchmark.java.
Seeing a red underline or compile error?
Make sure benchmarkCoinChange is placed inside the DPBenchmark class braces but outside the main method.
Check that the method calls CoinChange.coinChangeRecursive, CoinChange.coinChangeMemo, and CoinChange.coinChangeTabulation with the class prefix. These are public static methods in CoinChange.java.
Help me fix a compile error in DPBenchmark.java
Add the House Robber benchmark with scaling demo
The House Robber benchmark tests all four optimization levels (including the space-optimized approach) and finishes with a summary of key takeaways.
- In DPBenchmark.java, add the benchmarkHouseRobber method between benchmarkCoinChange and generateHouses:
private static void benchmarkHouseRobber() {
System.out.println("=== HOUSE ROBBER BENCHMARK ===");
System.out.println();
int[] sizes = {10, 20, 25, 30};
System.out.printf("%-8s | %-15s | %-15s | %-15s | %-15s%n",
"Houses", "Recursion", "Memoization", "Tabulation", "Optimized");
System.out.println("-".repeat(78));
for (int size : sizes) {
int[] houses = generateHouses(size);
long start = System.nanoTime();
HouseRobber.robRecursive(houses);
long recursionTime = System.nanoTime() - start;
start = System.nanoTime();
HouseRobber.robMemo(houses);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
HouseRobber.robTabulation(houses);
long tabTime = System.nanoTime() - start;
start = System.nanoTime();
HouseRobber.robOptimized(houses);
long optTime = System.nanoTime() - start;
System.out.printf("%-8d | %-15s | %-15s | %-15s | %-15s%n",
size,
formatTime(recursionTime),
formatTime(memoTime),
formatTime(tabTime),
formatTime(optTime));
}
System.out.println();
System.out.println("Large input (1000 houses) - Recursion skipped (too slow):");
int[] largeHouses = generateHouses(1000);
long start = System.nanoTime();
int r2 = HouseRobber.robMemo(largeHouses);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
int r3 = HouseRobber.robTabulation(largeHouses);
long tabTime = System.nanoTime() - start;
start = System.nanoTime();
int r4 = HouseRobber.robOptimized(largeHouses);
long optTime = System.nanoTime() - start;
System.out.printf(" Memoization: $%d in %s%n", r2, formatTime(memoTime));
System.out.printf(" Tabulation: $%d in %s%n", r3, formatTime(tabTime));
System.out.printf(" Optimized: $%d in %s%n", r4, formatTime(optTime));
System.out.println();
System.out.println("=== KEY TAKEAWAYS ===");
System.out.println("1. Recursion: Exponential time - unusable for large inputs");
System.out.println("2. Memoization: Polynomial time - good default in interviews");
System.out.println("3. Tabulation: Same complexity, no stack overhead");
System.out.println("4. Space-Optimized: Same time, O(1) space - strong follow-up");
}What does this code do?
This method tests all four House Robber approaches across array sizes [10, 20, 25, 30]. The recursion column will show dramatic time growth as size increases, while the other three stay nearly instant.
The large-input section (1000 houses) skips recursion entirely. At that scale, O(2^n) recursion would never finish. The key takeaways summarize the interview wisdom: start with memoization, offer tabulation, and mention space optimization as a strong follow-up.
- Save DPBenchmark.java.
Methods not being found?
Verify that HouseRobber.robRecursive, HouseRobber.robMemo, HouseRobber.robTabulation, and HouseRobber.robOptimized match the method names in your HouseRobber.java exactly.
All three .java files must be in the same folder. Java resolves class references at compile time across files in the same directory.
Help me fix method-not-found errors in DPBenchmark
✔️ Awesome, I've got everything!
Great. Double check you have saved DPBenchmark.java before moving on to compile.
ⓧ I'd like to double check the full code
public class DPBenchmark {
public static void main(String[] args) {
System.out.println("==================================================");
System.out.println(" Dynamic Programming Benchmark Suite ");
System.out.println("==================================================");
System.out.println();
benchmarkCoinChange();
System.out.println();
benchmarkHouseRobber();
}
private static void benchmarkCoinChange() {
System.out.println("=== COIN CHANGE BENCHMARK ===");
System.out.println("Coins: [1, 5, 10, 25]");
System.out.println();
int[] coins = {1, 5, 10, 25};
int[] testAmounts = {10, 20, 30, 36, 50};
System.out.printf("%-8s | %-15s | %-15s | %-15s%n",
"Amount", "Recursion", "Memoization", "Tabulation");
System.out.println("-".repeat(62));
for (int amount : testAmounts) {
long start = System.nanoTime();
CoinChange.coinChangeRecursive(coins, amount);
long recursionTime = System.nanoTime() - start;
start = System.nanoTime();
CoinChange.coinChangeMemo(coins, amount);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
CoinChange.coinChangeTabulation(coins, amount);
long tabTime = System.nanoTime() - start;
System.out.printf("%-8d | %-15s | %-15s | %-15s%n",
amount,
formatTime(recursionTime),
formatTime(memoTime),
formatTime(tabTime));
}
System.out.println();
System.out.println("Large input (amount = 200) - Recursion skipped (too slow):");
int largeAmount = 200;
long start = System.nanoTime();
int r2 = CoinChange.coinChangeMemo(coins, largeAmount);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
int r3 = CoinChange.coinChangeTabulation(coins, largeAmount);
long tabTime = System.nanoTime() - start;
System.out.printf(" Memoization: %d coins in %s%n", r2, formatTime(memoTime));
System.out.printf(" Tabulation: %d coins in %s%n", r3, formatTime(tabTime));
}
private static void benchmarkHouseRobber() {
System.out.println("=== HOUSE ROBBER BENCHMARK ===");
System.out.println();
int[] sizes = {10, 20, 25, 30};
System.out.printf("%-8s | %-15s | %-15s | %-15s | %-15s%n",
"Houses", "Recursion", "Memoization", "Tabulation", "Optimized");
System.out.println("-".repeat(78));
for (int size : sizes) {
int[] houses = generateHouses(size);
long start = System.nanoTime();
HouseRobber.robRecursive(houses);
long recursionTime = System.nanoTime() - start;
start = System.nanoTime();
HouseRobber.robMemo(houses);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
HouseRobber.robTabulation(houses);
long tabTime = System.nanoTime() - start;
start = System.nanoTime();
HouseRobber.robOptimized(houses);
long optTime = System.nanoTime() - start;
System.out.printf("%-8d | %-15s | %-15s | %-15s | %-15s%n",
size,
formatTime(recursionTime),
formatTime(memoTime),
formatTime(tabTime),
formatTime(optTime));
}
System.out.println();
System.out.println("Large input (1000 houses) - Recursion skipped (too slow):");
int[] largeHouses = generateHouses(1000);
long start = System.nanoTime();
int r2 = HouseRobber.robMemo(largeHouses);
long memoTime = System.nanoTime() - start;
start = System.nanoTime();
int r3 = HouseRobber.robTabulation(largeHouses);
long tabTime = System.nanoTime() - start;
start = System.nanoTime();
int r4 = HouseRobber.robOptimized(largeHouses);
long optTime = System.nanoTime() - start;
System.out.printf(" Memoization: $%d in %s%n", r2, formatTime(memoTime));
System.out.printf(" Tabulation: $%d in %s%n", r3, formatTime(tabTime));
System.out.printf(" Optimized: $%d in %s%n", r4, formatTime(optTime));
System.out.println();
System.out.println("=== KEY TAKEAWAYS ===");
System.out.println("1. Recursion: Exponential time - unusable for large inputs");
System.out.println("2. Memoization: Polynomial time - good default in interviews");
System.out.println("3. Tabulation: Same complexity, no stack overhead");
System.out.println("4. Space-Optimized: Same time, O(1) space - strong follow-up");
}
private static int[] generateHouses(int n) {
int[] houses = new int[n];
for (int i = 0; i < n; i++) {
houses[i] = (i * 7 + 3) % 20 + 1;
}
return houses;
}
private static String formatTime(long nanos) {
if (nanos < 1_000) {
return nanos + " ns";
} else if (nanos < 1_000_000) {
return String.format("%.1f us", nanos / 1_000.0);
} else if (nanos < 1_000_000_000) {
return String.format("%.2f ms", nanos / 1_000_000.0);
} else {
return String.format("%.2f s", nanos / 1_000_000_000.0);
}
}
}Compile and run all files together
Because DPBenchmark references classes defined in the other two files, you need to compile all three together so Java can resolve the cross-file method calls.
- Compile all three files at once by running this command:
javac *.java- Run the benchmark suite by running:
java DPBenchmarkWhat should I see?
You will see two formatted tables. In the Coin Change table, the Recursion column grows dramatically from amount 10 to amount 50. The Memoization and Tabulation columns stay in the microsecond range throughout.
In the House Robber table, recursion time visibly increases with each row (especially at 25 and 30 houses), while all other columns remain nearly instant. The large-input sections confirm that memoization, tabulation, and space-optimized approaches handle inputs of 200 or 1000 without breaking a sweat.
- Confirm that the KEY TAKEAWAYS section prints at the bottom of the output.
- Verify that all result values match between approaches (memoization and tabulation should produce identical coin counts and loot values).
Seeing a compile error?
Make sure all three files (CoinChange.java, HouseRobber.java, DPBenchmark.java) are in the same dp-interview-lab folder.
If you see "cannot find symbol" errors, check that your method names and parameter types match exactly. For example, coinChangeRecursive takes int[] and int as arguments.
Help me fix compile errors when building DPBenchmark
Why skip recursion for large inputs?
Coin Change recursion is O(k^amount) and House Robber recursion is O(2^n). For amount = 200 or n = 1000, these would take longer than the age of the universe to complete. Skipping them is the honest thing to do in a benchmark. It also mirrors what you would say in an interview: acknowledge the exponential cost and move to the optimized solution.
Secret mission
Minimum Path Sum - 2D DP
You have mastered 1D DP with rolling variables. Now extend your framework to two dimensions. Solve Minimum Path Sum using all four optimization levels, and discover how a rolling 1D array replaces the 2D table.
Clean Up Your Resources
Clean Up Your Resources
This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project folder for future reference or delete it entirely.
Resources you used:
- The dp-interview-lab folder on your Desktop (contains Java source files and compiled .class files).
Keep everything running
No action needed. Choose this if you want to revisit your DP implementations, extend them with new problems, or use the benchmark suite as a reference for future interview prep.
- Your dp-interview-lab folder stays on your Desktop with all source and compiled files intact.
- You can re-run any benchmark at any time with java DPBenchmark from inside the folder.
Pause - I'll come back to this later
Since this is a local project with no running processes, there is nothing to pause. Your files sit idle on disk and consume no memory or CPU.
- Leave the dp-interview-lab folder as-is. It takes minimal disk space.
- When you return, open the folder in VS Code and pick up where you left off.
Delete - I don't want to use this again
Remove the entire project folder to start fresh. This deletes all Java source files and compiled class files permanently.
- On macOS or Linux, open your terminal and run:
rm -rf ~/Desktop/dp-interview-lab- On Windows, open PowerShell and run:
Remove-Item -Recurse -Force ~\Desktop\dp-interview-lab- Confirm the folder is gone by running ls ~/Desktop (macOS/Linux) or ls ~\Desktop (Windows). You should no longer see dp-interview-lab in the output.
Nice Work!
Nice Work!
You just built a complete Dynamic Programming laboratory in Java. You now have a repeatable framework for breaking down DP problems that interviewers love to ask.
Here's what you accomplished:
- Built 3 progressively optimized solutions for Coin Change (the Unbounded Knapsack pattern), going from exponential recursion to O(amount * coins) tabulation.
- Built 4 progressively optimized solutions for House Robber (the Linear DP pattern), achieving O(1) space with rolling variables.
- Created a benchmark suite that visually proves why each optimization step matters, from exponential explosion to constant-space elegance.
- Secret Mission: Extended the framework to 2D DP with Minimum Path Sum, including rolling-array space optimization that reduces O(m*n) space to O(n).
Ready to quiz yourself?