☕ DSA Java Articles

Topics › Dynamic Programming › Introduction to DP

Introduction to DP

Easy TUF ID 1195 A2Z

Java source ↗ Edit this article ↗

What dynamic programming is

Dynamic programming (DP) is recursion that never solves the same subproblem twice. You describe the answer to a problem in terms of answers to smaller versions of the same problem (a recurrence), and you store each smaller answer the first time you compute it. That is all it is. The hard part is never the caching; it is finding the right recurrence.

A problem is a good fit for DP when two things are true:

  1. Overlapping subproblems. A plain recursion reaches the same state (the same arguments) many times. Caching only pays off if there is something to reuse.
  2. Optimal substructure. The answer for a state can be built from the answers of smaller states, and those smaller answers do not depend on how you got to them.

Merge sort is a useful contrast. It also splits a problem into smaller ones, but the two halves never overlap, so a cache would never get a hit. That is divide and conquer, not DP.

In practice, DP problems ask you to count the ways to do something, find the minimum or maximum cost of doing it, or decide whether it can be done at all, where the input forces a sequence of choices.

This article uses the Fibonacci numbers to show the four forms every DP solution in this sheet goes through: plain recursion, memoization, tabulation and space optimization. Every method lives in the Java file and is checked against known values.

The running example: Fibonacci

F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n ≥ 2. The sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

n = 5   ->  5
n = 10  ->  55

Step 0: Plain recursion

Translate the definition directly. The two base cases stop the recursion; every other call makes two recursive calls. The static counter calls is only there so the test can measure how much work this does.

static long plainRecursion(int n) {
    calls++;
    if (n <= 1) return n;                                   // base cases: F(0) = 0, F(1) = 1
    return plainRecursion(n - 1) + plainRecursion(n - 2);
}

Here is the call tree for n = 4:

                 f(4)
              /        \
          f(3)          f(2)       <- f(2) computed here...
         /    \        /    \
      f(2)    f(1)   f(1)   f(0)
     /    \
   f(1)  f(0)                      <- ...and again here

Nine calls to produce the number 3. f(2) is solved twice and f(1) three times. The waste compounds: f(n - 2) is solved once directly and again inside f(n - 1), so the number of calls obeys the same recurrence as Fibonacci itself. Exactly 2F(n + 1) - 1 calls are made, which grows like 1.618^n:

n calls
10 177
20 21,891
30 2,692,537
40 331,160,281
50 about 4 × 10^10

Yet there are only n + 1 distinct subproblems, f(0) through f(n). That gap between “calls made” and “distinct states” is the signal that DP applies.

Time O(2^n) (more precisely O(1.618^n)), stack space O(n) because the deepest chain is f(n), f(n-1), ..., f(1).

Technique 1: Memoization (top-down)

Keep the recursion exactly as it is and add a table. Three edits turn any recursion into memoized recursion:

  1. Create a table dp with one cell per possible state, filled with a value that cannot be a real answer (here -1).
  2. At the start of the call, if dp[n] is filled, return it.
  3. Before returning a freshly computed answer, store it in dp[n].
static long memoization(int n) {
    long[] dp = new long[n + 1];
    Arrays.fill(dp, -1);                                    // -1 means "not computed yet"
    return memo(n, dp);
}

static long memo(int n, long[] dp) {
    memoCalls++;
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];                          // solved before: answer in O(1)
    return dp[n] = memo(n - 1, dp) + memo(n - 2, dp);      // solve once, store, return
}

Why does this make only 2n - 1 calls? memo(n) first calls memo(n - 1), which recursively fills every cell from 2 up to n - 1. When control comes back and memo(n) asks for memo(n - 2), the answer is already in the table, so that call returns at once. The tree collapses into a chain with one short leaf hanging off each level. For n = 20 the test asserts 39 calls instead of 21,891.

Time O(n): each of the n + 1 states is computed once, in O(1) work besides its recursive calls. Space O(n) for the table plus O(n) for the recursion stack.

The sentinel must be impossible as a real answer. Fibonacci numbers are never negative, so -1 is safe. When answers can be negative (minimum path sums, for example) use something like Integer.MAX_VALUE or a Boolean/boxed table instead.

Technique 2: Tabulation (bottom-up)

Memoization works backwards from n and lets recursion discover the order. Tabulation flips the direction: start at the base cases and fill the table forward, in an order where every cell’s dependencies are already filled when you reach it. For Fibonacci, dp[i] needs dp[i - 1] and dp[i - 2], so a plain left-to-right loop works.

The recipe is mechanical:

  1. Declare the same table the memoized version used.
  2. Write the base cases into it.
  3. Loop over the states in dependency order.
  4. Copy the recurrence, replacing each recursive call with a table read.
static long tabulation(int n) {
    if (n <= 1) return n;
    long[] dp = new long[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Dry run for n = 6:

i 0 1 2 3 4 5 6
dp[i] 0 1 1 2 3 5 8

Time O(n), space O(n) for the table, and no recursion at all. That last point matters in Java: a memoized recursion 100,000 levels deep will usually throw StackOverflowError with the default thread stack, while the loop does not care how large n is.

Technique 3: Space optimization

Look at what the loop reads: only the previous two cells. Everything older is dead weight. Keep two variables instead of the array:

static long spaceOptimized(int n) {
    if (n <= 1) return n;
    long prev2 = 0, prev = 1;                               // F(i - 2) and F(i - 1), starting at i = 2
    for (int i = 2; i <= n; i++) {
        long cur = prev + prev2;
        prev2 = prev;
        prev = cur;
    }
    return prev;
}

The order of the three assignments matters. Compute cur from the old values first, then shift: prev2 takes the old prev, and prev takes cur. Writing prev = cur first would lose the value prev2 needs.

Time O(n), space O(1).

The same idea scales up. When a grid DP’s row i depends only on row i - 1, you keep one or two rows instead of the whole grid; when a state depends on the last k cells, you keep a window of k. You will see both in the problems that follow.

Comparing the four forms

Form Time Extra space Recursion When to use
Plain recursion O(1.618^n) O(n) stack yes only to write down the recurrence
Memoization O(n) O(n) table + O(n) stack yes fastest to write once the recursion is right
Tabulation O(n) O(n) table no large inputs, no stack risk
Space optimized O(n) O(1) no when only a fixed window of the table is read

In an interview, write the recursion first, because it is where the thinking happens. Memoize it, then convert to tabulation and trim the space if asked. Each step is a mechanical rewrite of the previous one, which is why the recursion has to be right.

A recipe for writing the recurrence

Most problems in this sheet yield to the same three questions:

  1. What is the state? Express the problem in terms of an index (or a few): “f(i) is the answer for the first i elements” or “for the cell (i, j)”. Say precisely in words what f(i) means.
  2. What choices exist at that state? Try all of them: take the element or skip it, jump one step or two, come from above or from the left.
  3. How are the choices combined? Add them when counting ways, take the min or max when optimizing, OR them when asking whether something is possible.

Then write the base cases: the smallest states whose answers are obvious.

Fibonacci has no real choices, but the next problems do. In Climbing Stairs, f(i) is the number of ways to reach step i, the last move was either a 1-step or a 2-step, and the counts add. In Frog Jump, f(i) is the cheapest way to reach stair i, the same two last moves exist, and you take the minimum.

Pitfalls