🧠 Data Structures & Algorithms · Advanced

Dynamic programming in Java

Overlapping subproblems, memoization vs tabulation.

🧩 The mysteryNaive recursion asks the same question again and again, millions of times. Dynamic programming writes the answer down once, like memorizing 7 x 8 instead of counting on your fingers.

Same question, asked again

Naive Fibonacci calls fib(n - 1) and fib(n - 2), and both branches recompute the same values. fib(5) computes fib(3) twice and fib(2) three times; the call count grows exponentially. That repeated work is called overlapping subproblems.

int fib(int n) {
    return n < 2 ? n
        : fib(n - 1) + fib(n - 2);
}

🔮 Predict it

Count the calls

What does this print?

int calls = 0;
int fib(int n) {
    calls++;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
void main() {
    fib(4);
    System.out.println(calls);
}

9
4
5
16

Show the answer

fib(4) calls fib(3) and fib(2); fib(3) calls fib(2) and fib(1); and so on. Counting every call: fib(0) and fib(1) cost 1, fib(2) costs 3, fib(3) costs 5, fib(4) costs 1 + 5 + 3 = 9. fib(5) would cost 15.

Memoization: top-down

Memoization keeps the recursion but adds a cache: before computing, check if the answer is already stored. Each subproblem is now solved once, so Fibonacci drops from exponential to O(n). It only computes the states the recursion actually reaches.

long[] memo = new long[91];
long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Tabulation: bottom-up

Tabulation drops recursion and fills a table from the smallest cases up. Ways to climb n stairs taking 1 or 2 steps: the last move came from i - 1 or i - 2, so dp[i] = dp[i - 1] + dp[i - 2]. No deep recursion, and often only the last few entries are needed, giving O(1) space.

int[] dp = new int[n + 1];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
// 1, 1, 2, 3, 5, 8, ...

🔮 Predict it

Stairs with a 3-step

Now you may climb 1, 2 or 3 steps at a time. How many ways to climb 4 stairs?

int n = 4;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++)
    for (int s = 1; s <= 3; s++)
        if (i - s >= 0) dp[i] += dp[i - s];
System.out.println(dp[n]);

Show the answer

Build up from the bottom: dp[0] = 1, dp[1] = 1, dp[2] = 1 + 1 = 2, dp[3] = 2 + 1 + 1 = 4, dp[4] = 4 + 2 + 1 = 7. Each entry reuses smaller, already-solved entries.

⚠️ The trap

Not everything is DP

DP needs overlapping subproblems (the same small problem is solved repeatedly) and optimal substructure (the best answer is built from best sub-answers). Fewest coins for an amount, longest common subsequence and 0/1 knapsack qualify. Finding the max of an array is one pass with nothing to reuse: not DP.

🤔 Think first

Same work either way?

Do memoization and tabulation always compute exactly the same set of subproblems?

Think about it, then reveal the answer

No. Tabulation fills the whole table, every state from the bottom up. Memoization computes only the states the recursion actually reaches, which can be far fewer. Tabulation, in return, avoids deep recursion and stack overflows.

💼 In the real world

DP in the real world

Diff tools use longest common subsequence, spell checkers use edit distance, and route planners and pricing engines use DP tables. In interviews, spotting the recurrence (like dp[i] from dp[i - 1] and dp[i - 2]) is the key step.

Key takeaways

Overlapping subproblems + optimal substructure → DP
Memoization: recursive, computes only the states it needs
Tabulation: iterative, no deep recursion
Often only the last few entries are needed: O(1) space

💡 Writing down 7 × 8 = 56 once instead of recounting on your fingers every time.

🤯 Did you know?

Richard Bellman picked the name "dynamic programming" in the 1950s partly because it sounded impressive and hid the fact that he was doing mathematical research, which a powerful official of the time disliked.

Practice questions

This counts the ways to climb 5 stairs taking 1 or 2 steps at a time. What does it print?

int n = 5;
int[] dp = new int[n + 1];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
System.out.println(dp[n]);

Check your answer

8. dp[i] counts the ways to climb i stairs taking 1 or 2 steps: 1, 1, 2, 3, 5, 8. Each entry is built from smaller, already-solved entries.

What does this print?

int calls = 0;
int fib(int n) {
    calls++;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
void main() {
    fib(5);
    System.out.println(calls);
}

Check your answer

15. The call tree branches twice per level and repeats work: fib(3) is computed 2 times and fib(2) 3 times. Calls grow exponentially; memoization makes the count linear.

Last stop in this world: two pointers, sliding windows, prefix sums and greedy, the tricks that turn O(n²) into O(n).