Dynamic Programming (DP) often feels like a magic trick when you first see it in a textbook, but in practice, it's just an optimization technique. At its heart, DP is just recursion where we stop doing the same work twice by remembering the results of sub-problems. I've found that the best way to master this isn't by memorizing formulas, but by following a specific evolution: starting with a "naive" recursive solution and incrementally refining it.

Tackling the Coin Change Problem

Let's look at a classic: given a set of coin denominations and a target amount, what is the minimum number of coins needed to make that amount? If we have coins of [1, 2, 5] and we want to make 11, the answer is 3 (5 + 5 + 1).

My first instinct is always to think recursively. To find the minimum for 11, I can try taking one coin of each denomination and then ask, "What's the minimum needed for the remaining amount?" It looks like this:

public int minCoins(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int res = minCoins(coins, amount - coin);
        if (res >= 0 && res < min) {
            min = 1 + res;
        }
    }
    return (min == Integer.MAX_VALUE) ? -1 : min;
}

This works for small numbers, but it's a nightmare for performance. If the amount is 100, we're recalculating the minimum for "amount = 50" thousands of times. We're essentially building a massive tree of redundant calls.

Adding a Cache to Stop the Bleeding

To fix this, we use "Top-Down" DP, also known as memoization. I'll just throw an array into the mix to store the results we've already calculated. If we hit the same amount twice, we return the cached value immediately.

public int minCoinsMemo(int[] coins, int amount) {
    return helper(coins, amount, new int[amount + 1]);
}

private int helper(int[] coins, int amount, int[] memo) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (memo[amount] != 0) return memo[amount];

    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int res = helper(coins, amount - coin, memo);
        if (res >= 0 && res < min) {
            min = 1 + res;
        }
    }

    memo[amount] = (min == Integer.MAX_VALUE) ? -1 : min;
    return memo[amount];
}

The "Integer Overflow" Trap

Now, here is where I usually trip up when I'm rushing through a coding interview or a tight deadline. I often try to simplify the logic by initializing my tracking variable to Integer.MAX_VALUE and then doing something like 1 + helper(...).

I once wrote a version of this where I didn't check if the recursive call returned -1 before adding 1 to it. In Java, Integer.MAX_VALUE + 1 wraps around to -2147483648. Suddenly, my "minimum" number of coins was a massive negative number, and the program told me I could make change for a million dollars using negative two billion coins. Always be careful when adding to "infinity" constants in Java.

Switching to a Bottom-Up Table

While memoization is great, recursion still has overhead (and can lead to a StackOverflowError if the amount is huge). The "professional" way to handle this is Tabulation. Instead of going from the target amount down to zero, we build the solution from zero up to the target.

I like this approach because it's iterative and usually faster. We create a dp array where dp[i] represents the minimum coins needed for amount i.

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // Initialize with amount + 1 because that's a value impossible to reach
    java.util.Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

Notice how I avoided Integer.MAX_VALUE here. By using amount + 1 as my "infinity," I completely eliminate the risk of integer overflow while still having a value that is guaranteed to be larger than any possible real solution.

📋 Practical Task

Exercise: Solving the House Robber Problem

You are tasked with writing a program for a thief who wants to rob houses along a street. Each house has a certain amount of money stored in it. However, the thief cannot rob two adjacent houses because the security systems are connected; if two neighboring houses are broken into on the same night, the police are alerted.

Your Goal: Implement a method public int rob(int[] nums) that calculates the maximum amount of money the thief can rob without alerting the police.

Requirements:

• Use a Bottom-Up Dynamic Programming approach (Tabulation).
• Your solution should have a time complexity of O(n) and a space complexity of O(n).
• Handle the edge case where the input array is empty or contains only one house.