Dynamic Programming Basics in Java

If someone asks you what 17 × 24 is, you work it out. If they ask again two minutes later, you don't multiply again; you remember the answer, 408. Now imagine a calculation that asks itself the same smaller question thousands of times. Remembering the answers turns hours of work into milliseconds. That simple idea, solve each smaller problem once and reuse the answer, is dynamic programming (DP). It sounds advanced, but most DP solutions are a loop and an array. In this lesson, you will learn when a problem suits DP, the two ways to write it (memoization and tabulation), and solve two classic problems in Java.

What Is Dynamic Programming?

Dynamic programming in Java is a technique that is used to solve a problem by breaking it into smaller subproblems, solving each subproblem only once, and storing its answer so it can be reused whenever it is needed again.

A problem suits DP when it has two properties:

If the subproblems don't overlap (as in merge sort, where each half is different), plain recursion is enough.

The Problem with Plain Recursion

The Fibonacci numbers start 0, 1, and each next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, ... The recursive definition is short, but it recomputes the same values over and over. Let's see how many calls it makes.

public class NaiveFib {
    static long calls = 0;
 
    static long fib(int n) {
        calls++;
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }
 
    public static void main(String[] args) {
        for (int n : new int[] {10, 20, 30}) {
            calls = 0;
            long value = fib(n);
            System.out.println("fib(" + n + ") = " + value
                    + " using " + calls + " calls");
        }
    }
}

fib(10) = 55 using 177 calls
fib(20) = 6765 using 21891 calls
fib(30) = 832040 using 2692537 calls

Explanation: fib(30) needs well over a million calls, because fib(28) is computed twice, fib(27) three times, fib(26) five times, and so on. The work grows roughly like 2ⁿ. Yet there are only 31 different questions: fib(0) to fib(30).

Approach 1: Memoization (Top-Down)

Memoization keeps the recursive method but stores each answer the first time it is computed. Before computing, the method checks whether the answer is already stored.

public class MemoFib {
    static long calls = 0;
    static long[] memo = new long[91];
 
    static long fib(int n) {
        calls++;
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];       // already solved
        memo[n] = fib(n - 1) + fib(n - 2);      // solve once, store
        return memo[n];
    }
 
    public static void main(String[] args) {
        long f30 = fib(30);
        System.out.println("fib(30) = " + f30 + " using " + calls + " calls");
        calls = 0;
        long f90 = fib(90);
        System.out.println("fib(90) = " + f90 + " using " + calls + " calls");
    }
}

fib(30) = 832040 using 59 calls
fib(90) = 2880067194370816120 using 121 calls

Explanation: with the memo array, fib(30) needs only 59 calls instead of more than a million, and fib(90) is instant. (Its later run is even cheaper, because answers up to 30 were already stored.) The time is now O(n), at the cost of O(n) memory for the array.

Approach 2: Tabulation (Bottom-Up)

Tabulation drops the recursion. It fills a table from the smallest subproblem upwards, so every answer it needs is already in the table.

public class TableFib {
    static long fib(int n) {
        if (n <= 1) return n;
        long[] table = new long[n + 1];
        table[0] = 0;
        table[1] = 1;
        for (int i = 2; i <= n; i++) {
            table[i] = table[i - 1] + table[i - 2];
        }
        return table[n];
    }
 
    public static void main(String[] args) {
        System.out.println("fib(30) = " + fib(30));
        System.out.println("fib(90) = " + fib(90));
    }
}

fib(30) = 832040
fib(90) = 2880067194370816120

Explanation: the loop computes fib(2), then fib(3), and so on, each from the two entries before it. There is no recursion, so there is no risk of StackOverflowError. Since each step needs only the last two values, you could even replace the array with two variables and use O(1) memory.

A Classic: Coin Change

What is the smallest number of coins that make a given amount? With coins 1, 3 and 4 and an amount of 6, the greedy idea "always take the biggest coin" gives 4 + 1 + 1 (three coins), but the best answer is 3 + 3 (two coins). DP finds the true minimum.

The DP table best[a] holds the fewest coins for amount a. For each amount, try every coin c and take 1 + best[a - c]:

import java.util.Arrays;
 
public class CoinChange {
    static int minCoins(int[] coins, int amount) {
        int[] best = new int[amount + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[0] = 0;                                   // zero coins make 0
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && best[a - c] != Integer.MAX_VALUE) {
                    best[a] = Math.min(best[a], best[a - c] + 1);
                }
            }
        }
        System.out.println("table: " + Arrays.toString(best));
        return best[amount] == Integer.MAX_VALUE ? -1 : best[amount];
    }
 
    public static void main(String[] args) {
        System.out.println("coins for 6: " + minCoins(new int[] {1, 3, 4}, 6));
        System.out.println("coins for 7: " + minCoins(new int[] {2, 4}, 7));
    }
}

table: [0, 1, 2, 1, 1, 2, 2]
coins for 6: 2
table: [0, 2147483647, 1, 2147483647, 1, 2147483647, 2, 2147483647]
coins for 7: -1

Explanation:

1. The first table matches the Markdown table above: 6 needs 2 coins.
2. With coins 2 and 4, no combination makes 7, so the entry stays at MAX_VALUE and the method returns -1.
3. Two nested loops over amount and the coins give O(amount × coins) time and O(amount) memory.

Classic DP Problems

Interview Corner

Practice

1. Easy: Write climbStairs(int n): the number of ways to climb n steps taking 1 or 2 at a time. It follows the same rule as Fibonacci. Check that climbStairs(5) is 8.
2. Harder: Extend CoinChange to also print which coins make the minimum, by storing for each amount the last coin used and walking back from amount.

Key Takeaways