Dynamic Programming in Java for Beginners: Memoization vs Tabulation (10 Classic Problems)

Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS) and JUnit 6.1.3 (latest GA on Maven Central; its latest and release entries agree). No other library is used: the ten solutions are plain Java. Everything quoted below comes from a committed file in the dynamic-programming module of the java-interview-lab repository. Timings are deliberately absent — the evidence here is counts, tables and exact outputs, which do not vary from machine to machine.

Plain recursion solves the same problem again and again

public static long naive(int n, long[] calls) {
    calls[0]++;
    if (n < 2) return n;
    return Math.addExact(naive(n - 1, calls), naive(n - 2, calls));
}

Fibonacci: how many calls does each approach make?
==================================================

n    fib(n)                 naive calls    memo calls     table steps
10   55                     177            19             9
20   6765                   21891          39             19
30   832040                 2692537        59             29
40   102334155              331160281      79             39

naive calls = every call the recursion made (counted, not predicted).
memo calls  = the same recursion with a notebook: 2n-1 calls, because each F(k) is computed once.
table steps = additions in the bottom-up loop (n-1).

Memoization: keep the recursion, add a notebook

private static long memo(int n, long[] notebook, long[] calls) {
    calls[0]++;
    if (n < 2) return n;
    if (notebook[n] != 0) return notebook[n];          // 0 means "not solved yet" (F(n) > 0 for n >= 1)
    return notebook[n] = Math.addExact(memo(n - 1, notebook, calls), memo(n - 2, notebook, calls));
}

The tempting one-liner that breaks. Java maps have computeIfAbsent, and a recursive memo looks like a perfect fit: cache.computeIfAbsent(n, k -> f(k-1) + f(k-2)). With a HashMap it throws. The mapping function changes the map while computeIfAbsent is still working on it, and since JDK 9 HashMap detects that on a best-effort basis (the change was JDK-8071667; on JDK 8 the same code could silently leave a corrupt map). Look up, compute, then put:

public static long memoWithComputeIfAbsent(int n, Map<Integer, Long> cache) {
    if (n < 2) return n;
    return cache.computeIfAbsent(n, k -> memoWithComputeIfAbsent(k - 1, cache) + memoWithComputeIfAbsent(k - 2, cache));
}

public static long memoWithGetAndPut(int n, Map<Integer, Long> cache) {
    if (n < 2) return n;
    Long hit = cache.get(n);
    if (hit != null) return hit;
    long value = memoWithGetAndPut(n - 1, cache) + memoWithGetAndPut(n - 2, cache);
    cache.put(n, value);
    return value;
}

1) HashMap.computeIfAbsent as the memo, recursive mapping function, n = 10
   -> java.util.ConcurrentModificationException
   same idea written as get / compute / put -> 55

Tabulation: start from the smallest answer and build upwards

public static long tabulation(int n) {
    if (n < 2) return n;
    long[] dp = new long[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = Math.addExact(dp[i - 1], dp[i - 2]);
    return dp[n];
}

Recursion depth is a real limit. A memoized solution recurses once per element of a chain, so a long input can end in StackOverflowError while the table version never recurses at all.

3) Recursion depth, House Robber with every house worth 1, in a thread with a 256 KB stack
   memo       n =    500 -> 250
   memo       n = 50,000 -> java.lang.StackOverflowError
   tabulation n = 50,000 -> 25000

The answer can outgrow the type. Fibonacci overflows a long at n = 93. The code uses Math.addExact, which throws instead of wrapping around, and the transcript shows what plain + would have returned: a confident negative number.

2) The answer outgrows a long
   fib(92) = 7540113804746346429
   fib(93) -> ArithmeticException: long overflow   (Math.addExact refuses to wrap around)
   plain + instead of addExact would silently return -6246583658587674878

A four-step recipe, practised on climbing stairs and house robber

1. State. What is the smallest description of a sub-question? (“the first k houses”, “amount a”, “the first i items with capacity w”.)
2. Recurrence. How is the answer for a state built from the answers to smaller states?
3. Base cases. Which states can be answered without looking at any other?
4. Order and answer. In what order are cells filled so that inputs are ready, and which cell holds the final answer?

public static long tabulation(int n) {
    long[] dp = new long[n + 2];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

public static int[] table(int[] money) {
    int[] dp = new int[money.length + 1];
    for (int k = 1; k <= money.length; k++) {
        int skip = dp[k - 1];
        int take = (k >= 2 ? dp[k - 2] : 0) + money[k - 1];
        dp[k] = Math.max(skip, take);
    }
    return dp;
}

House Robber: money = [2, 7, 9, 3, 1]
=====================================

dp[k] = best total using only the first k houses
k      [0, 1, 2, 3, 4, 5]
dp[k]  [0, 2, 7, 11, 11, 12]

k=1  house worth 2: skip = dp[0] = 0, take = dp[0] + 2 = 2  ->  dp[1] = 2
k=2  house worth 7: skip = dp[1] = 2, take = dp[0] + 7 = 7  ->  dp[2] = 7
k=3  house worth 9: skip = dp[2] = 7, take = dp[1] + 9 = 11  ->  dp[3] = 11
k=4  house worth 3: skip = dp[3] = 11, take = dp[2] + 3 = 10  ->  dp[4] = 11
k=5  house worth 1: skip = dp[4] = 11, take = dp[3] + 1 = 12  ->  dp[5] = 12

answer = 12 (houses worth 2, 9 and 1)

Cross-check: 300 random inputs per problem, every variant must agree (seed 2026)
================================================================================
problem                      cases    variants compared
Climbing Stairs              300      memo = table = two variables (n up to 39)
House Robber                 300      memo = table = two variables

Space optimisation: remember only what you will read again

public static int twoVariables(int[] money) {
    int prev2 = 0, prev1 = 0;                          // best up to two houses ago, best up to the previous house
    for (int m : money) {
        int best = Math.max(prev1, prev2 + m);
        prev2 = prev1;
        prev1 = best;
    }
    return prev1;
}

What you give up. Once cells are discarded you cannot walk back through the table to find which houses were robbed, only how much. If the interviewer asks for the choices and not just the total, keep the table. The LCS section shows the same trade-off with letters.

Coin change: greedy looks right and is wrong

public static int tabulation(int[] coins, int amount) {
    int impossible = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, impossible);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] >= impossible ? -1 : dp[amount];
}

Coin Change: greedy, the overflow bug, call counts, loop order
==============================================================

1) Greedy fails: coins {1,3,4}, amount 6
   greedy      -> 3 coins (4+1+1)
   DP (table)  -> 2 coins (3+3)

2) 'Impossible' = Integer.MAX_VALUE, then dp[a-c] + 1: coins {2}, amount 3 (really impossible)
   correct (impossible = amount + 1) -> -1
   Integer.MAX_VALUE version         -> -2147483648

3) Calls made: coins {1,2,5}, amount 27, answer 6
   naive recursion -> 2688332 calls
   memoized        -> 77 calls

4) Loop order changes the question: coins {1,2,5}, amount 5
   coins in the OUTER loop  -> 4 (combinations: 5 / 2+2+1 / 2+1+1+1 / 1x5)
   amount in the OUTER loop -> 9 (permutations: 1+2 and 2+1 now count separately)

2. The overflow that returns a negative answer. A common version fills the table with Integer.MAX_VALUE as “impossible” and then evaluates dp[a - c] + 1. Adding 1 to MAX_VALUE wraps around to MIN_VALUE, which looks like a fantastic (negative) coin count and wins every Math.min. For coins {2} and amount 3, the correct answer is −1 (impossible) and this version returns −2147483648. The fix is an “impossible” value that is large but cannot overflow when you add 1: amount + 1.

public static int tabulationOverflowBug(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

public static long countCombinations(int[] coins, int amount) {
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    for (int c : coins) {
        for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
    }
    return ways[amount];
}

public static long countPermutations(int[] coins, int amount) {
    long[] ways = new long[amount + 1];
    ways[0] = 1;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) ways[a] += ways[a - c];
        }
    }
    return ways[amount];
}

Longest increasing subsequence: the state can mean “ending here”

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

Longest Increasing Subsequence: [10, 9, 2, 5, 3, 7, 101, 18]
============================================================

a[i]  [10, 9, 2, 5, 3, 7, 101, 18]
dp[i] [1, 1, 1, 2, 2, 3, 4, 4]   (dp[i] = longest increasing subsequence ENDING at index i)

answer = max(dp) = 4 (for example 2, 3, 7, 18)
O(n log n) patience version = 4

Two choices per item: 0/1 knapsack

public static int[][] table(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w];
            if (weight[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w], value[i - 1] + dp[i - 1][w - weight[i - 1]]);
            }
        }
    }
    return dp;
}

1) Table: weights [1,3,4,5], values [1,4,5,7], capacity 7. dp[i][w] = best value with the first i items
w =        0   1   2   3   4   5   6   7
none       0   0   0   0   0   0   0   0
item 1     0   1   1   1   1   1   1   1
item 2     0   1   1   4   5   5   5   5
item 3     0   1   1   4   5   6   6   9
item 4     0   1   1   4   5   7   8   9
answer = dp[4][7] = 9 (weights 3 + 4, values 4 + 5)

public static int oneRowBackward(int[] weight, int[] value, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = capacity; w >= weight[i]; w--) {
            dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
        }
    }
    return dp[capacity];
}

public static int oneRowForwardBug(int[] weight, int[] value, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = weight[i]; w <= capacity; w++) {
            dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
        }
    }
    return dp[capacity];
}

2) One row, capacity loop direction: weights [5,4,6,3], values [10,40,30,50], capacity 10
   backward loop (each item used once) -> 90
   forward loop, same code otherwise   -> 150  (the weight-3 item is reused three times: 3 x 50)

The fingerprint of the wrong loop direction. The two methods differ only in the direction of the inner loop. Weights [5, 4, 6, 3], values [10, 40, 30, 50], capacity 10: the backward version returns 90 (the weight-4 and weight-3 items), the forward version returns 150 — the weight-3 item counted three times, which no bag could hold. If a 0/1 knapsack answer looks suspiciously high, check the loop direction first.

3) Calls made: 22 items, capacity 60, best value 357
   naive recursion -> 1003985 calls
   memoized        -> 1794 calls

Two strings, two dimensions: longest common subsequence and edit distance

public static int[][] table(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                    ? dp[i - 1][j - 1] + 1
                    : Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp;
}

           -   B   D   C   A   B   A
-          0   0   0   0   0   0   0
A          0   0   0   0   1   1   1
B          0   1   1   1   1   2   2
C          0   1   1   2   2   2   2
B          0   1   1   2   2   3   3
D          0   1   2   2   2   3   3
A          0   1   2   2   3   3   4
B          0   1   2   2   3   4   4

public static String reconstruct(String a, String b, int[][] dp) {
    StringBuilder sb = new StringBuilder();
    int i = a.length(), j = b.length();
    while (i > 0 && j > 0) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            sb.append(a.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return sb.reverse().toString();
}

length (bottom-right cell)       = 4
reconstructed from the full table = "BCBA"  (a valid subsequence of both strings)
two-row version                   = 4  (length only; cannot rebuild the string)

public static int twoRows(String a, String b) {
    int[] prev = new int[b.length() + 1];
    int[] curr = new int[b.length() + 1];
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            curr[j] = a.charAt(i - 1) == b.charAt(j - 1)
                    ? prev[j - 1] + 1
                    : Math.max(prev[j], curr[j - 1]);
        }
        int[] tmp = prev; prev = curr; curr = tmp;
    }
    return prev[b.length()];
}

public static int[][] table(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 0; i <= a.length(); i++) dp[i][0] = i;
    for (int j = 0; j <= b.length(); j++) dp[0][j] = j;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                    ? dp[i - 1][j - 1]
                    : 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
        }
    }
    return dp;
}

Edit Distance: "kitten" -> "sitting"
====================================

           -   s   i   t   t   i   n   g
-          0   1   2   3   4   5   6   7
k          1   1   2   3   4   5   6   7
i          2   2   1   2   3   4   5   6
t          3   3   2   1   2   3   4   5
t          4   4   3   2   1   2   3   4
e          5   5   4   3   2   2   3   4
n          6   6   5   4   3   3   2   3

answer = 3 (k->s, e->i, insert g)
two-row version = 3
horse -> ros           = 3
intention -> execution = 5

Grids and subsets: unique paths and partition equal subset sum

public static long oneRow(int rows, int cols) {
    long[] row = new long[cols];
    java.util.Arrays.fill(row, 1);
    for (int r = 1; r < rows; r++) {
        for (int col = 1; col < cols; col++) row[col] += row[col - 1];
    }
    return row[cols - 1];
}

Unique Paths on a 3 x 7 grid (right and down only)
==================================================

           0   1   2   3   4   5   6
row 0      1   1   1   1   1   1   1
row 1      1   2   3   4   5   6   7
row 2      1   3   6  10  15  21  28

answer = bottom-right cell = 28
10 x 10 grid: table = 48620, one row = 48620, binomial C(18,9) = 48620

public static boolean oneRow(int[] nums) {
    int total = Arrays.stream(nums).sum();
    if (total % 2 != 0) return false;
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int x : nums) {
        for (int s = target; s >= x; s--) dp[s] = dp[s] || dp[s - x];
    }
    return dp[target];
}

Partition Equal Subset Sum: [1, 5, 11, 5], target 11
====================================================

T = some subset of the first i numbers sums to s
s =        0   1   2   3   4   5   6   7   8   9  10  11
none       T   .   .   .   .   .   .   .   .   .   .   .
+1         T   T   .   .   .   .   .   .   .   .   .   .
+5         T   T   .   .   .   T   T   .   .   .   .   .
+11        T   T   .   .   .   T   T   .   .   .   .   T
+5         T   T   .   .   .   T   T   .   .   .   T   T

[1, 5, 11, 5] -> true  (5 + 5 + 1 = 11 = 11)
[1, 2, 3, 5] -> false  (total 11 is odd)
[1, 2, 4] -> false  (total 7 is odd)

Should you use a table at all? Unique paths has a closed formula, and the transcript shows it agreeing with the DP. When a formula or a provably correct greedy rule exists, it beats a table in time and in code. DP earns its place when the choices genuinely interact, as in knapsack, edit distance and coin change.

Why the two-row table is not a micro-optimisation

max heap (MiB)        : 48
strings               : two of length 5000
full table cells      : 25010001 ints = 100 MB
two-row cells         : 10002 ints = 40 KB
two rows LCS length   : 2500
full table LCS length : java.lang.OutOfMemoryError: Java heap space

It is a memory problem, not a correctness problem. Give the JVM a larger heap and both versions return the same length, which is also what the random cross-check asserts on small inputs. Space optimisation is what lets the same algorithm scale to inputs the table cannot hold.

All ten problems on one page

Cross-check: 300 random inputs per problem, every variant must agree (seed 2026)
================================================================================

problem                      cases    variants compared
Climbing Stairs              300      memo = table = two variables (n up to 39)
House Robber                 300      memo = table = two variables
Coin Change (fewest)         300      naive = memo = table (amount up to 29)
Longest Increasing Subseq.   300      memo = O(n^2) table = O(n log n) patience
0/1 Knapsack                 300      naive = memo = 2-D table = one row (backward)
Longest Common Subsequence   300      naive = memo = full table = two rows
Edit Distance                300      memo = full table = two rows
Unique Paths                 300      memo = table = one row = binomial formula
Partition Equal Subset Sum   300      memo = 2-D table = one row (backward)

Fibonacci is cross-checked in 01-fibonacci-call-counts.txt (naive = memo = table = two variables).

How to recognise a dynamic programming problem in an interview

• The question asks for a maximum, minimum, count or yes/no over many ways of choosing something (items, coins, moves, characters).
• The brute-force answer is a tree of choices, and when you draw a few levels the same sub-question appears in several branches.
• You can describe the answer for a smaller input and then build the bigger answer from it. If you can write “the best for the first k items” or “the answer for amount a”, you have a state.
• The state values are small integers: lengths, indices, capacities. If a state would be an arbitrary set, a table is not an option.

Should you reach for DP at all? Not always. A provably correct greedy rule or a closed formula (unique paths) is simpler and faster. A table is a poor fit when the state space is enormous — knapsack with a capacity in the billions — or when a question needs the full set of optimal answers rather than one. And if you cannot state the recurrence in a sentence, writing a table will not help: the fix is to find the state, not to type more code.

Download and run the code

cd dynamic-programming
mvn test
./scripts/run-all.sh

java DynamicProgrammingTenProblems.java

FAQ

Further reading

• Companion repository: java-interview-lab / dynamic-programming — the ten solutions, the tests and every transcript quoted here.
• LRU Cache in Java — another interview classic built from a map and a list, with the same “run it and quote the output” approach.
• HashMap vs ConcurrentHashMap — useful background for the computeIfAbsent trap in the memoization section.
• Tail vs non-tail recursion in Java and Fibonacci series in Java.
• Java 25 API: HashMap (see computeIfAbsent) and Math.addExact.
• JDK-8071667 — the bug whose fix made recursive computeIfAbsent throw ConcurrentModificationException from JDK 9.