What DP really is

Dynamic programming is a terrible name

Let's clear this up first, because the name puts people off before they start. 'Dynamic programming' has nothing to do with dynamic anything, and nothing to do with programming as you use the word. Richard Bellman picked it in the 1950s partly because it sounded impressive to a government funding committee.

Here is the honest definition: dynamic programming is recursion that remembers answers it has already worked out. That is genuinely all it is.

If chapter 3 made you comfortable with recursion, you are most of the way there already. What remains is noticing when a recursion is wasting time re-solving identical sub-problems, and giving it somewhere to write results down.

People find DP hard because they meet it as a grid of numbers to fill in, with no explanation of where the grid came from. We are going to arrive at the grid last, from the recursion, which is the order that makes it obvious.

The waste, made visible

Fibonacci is the clearest demonstration ever built, so we will use it even though nobody needs fast Fibonacci.

The naive recursion is a direct translation of the definition: fib(n) is fib(n-1) plus fib(n-2). Correct, elegant, and catastrophically slow - because fib(n-1) and fib(n-2) both go on to compute fib(n-3), separately, from scratch, and so does everything below them.

Count the calls and the problem is undeniable. fib(30) makes over 2.6 million calls to compute 31 distinct values. The same handful of answers are recomputed millions of times.

That is the signal you are looking for, and it has a name: overlapping subproblems. When the same sub-question arises repeatedly along different branches, the fix is to answer it once.

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);   // both branches redo the same work
}

fib(5) call tree - notice fib(2) appearing three times:

              fib(5)
          /            \
      fib(4)          fib(3)
     /     \          /    \
  fib(3)  fib(2)   fib(2)  fib(1)
  /    \
fib(2) fib(1)

n=20    calls    21,891       instant
n=30    calls    2,692,537    ~15 ms
n=40    calls    331,160,281  ~1.7 s
n=50    calls    ~40 billion  minutes

Memoisation: the fix is four lines

Memoisation means: before computing, check whether you already know the answer; after computing, write it down. The recursion is untouched otherwise - same shape, same base case, same recursive calls.

That single change collapses the call tree. Each distinct value is computed once and read thereafter, so the work drops from exponential to O(n) - one computation per distinct sub-problem.

This is the top-down form of DP: you still start at the big problem and recurse down, you just stop repeating yourself. It is the form to write first, every time, because it follows directly from the recursion you already understand.

Map<Integer, Long> memo = new HashMap<>();

long fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);   // 1. already known?

    long result = fib(n - 1) + fib(n - 2);         // 2. the SAME recursion
    memo.put(n, result);                           // 3. write it down
    return result;
}

n=30   naive 2,692,537 calls   memoised 59 calls
n=50   naive ~40 billion       memoised 99 calls
n=90   naive impossible        memoised 179 calls, instant

exponential -> O(n), from three added lines

Memoisation is a mechanical transformation

The step from a slow recursion to a fast one is not creative. It is a transformation you can apply without understanding the problem, and knowing that removes most of the fear around DP.

Three edits, always the same. One: at the top of the function, if the cache holds an answer for these arguments, return it. Two: compute as before. Three: store the result before returning it.

The only judgement required is what the cache key should be, and the rule is simple: the key is whatever arguments change between calls. If the function takes (i, capacity) and both vary, the key is that pair. Anything constant across all calls - the input array, the target - is not part of the key.

Get that wrong in either direction and it breaks quietly. Too few things in the key and different sub-problems collide, returning wrong answers. Too many and nothing ever hits the cache, so it is merely slow.

// BEFORE
int solve(int i, int budget) {
    if (i == n) return 0;
    return Math.max(solve(i + 1, budget), value[i] + solve(i + 1, budget - w[i]));
}

// AFTER - three edits, key = (i, budget), the arguments that VARY
Integer[][] memo = new Integer[n + 1][maxBudget + 1];

int solve(int i, int budget) {
    if (i == n) return 0;
    if (memo[i][budget] != null) return memo[i][budget];        // 1. check
    int result = Math.max(solve(i + 1, budget),                  // 2. compute
                          value[i] + solve(i + 1, budget - w[i]));
    return memo[i][budget] = result;                             // 3. store
}

n=20, budget=50

before   ~1,048,576 calls    exponential
after        ~1,071 calls    n x budget

states = 21 x 51 = 1,071 - each computed exactly once

Recap

Dynamic programming is recursion that remembers. The name is unhelpful and the idea is not.

Two conditions identify it. The answer must be expressible in terms of smaller versions of the same problem, and those smaller versions must repeat across different branches. Merge sort meets the first and not the second, which is why it needs no cache.

The routine never changes: write the recursion first, confirm sub-problems repeat, then add the three lines. The table comes later, and only if you need it.