Dynamic Programming

DP is recursion with the repeated work removed. That is the whole idea, and it is worth holding onto, because the reputation the topic has is out of proportion to it.

The hard part is never the memoisation — caching a function is mechanical. The hard part is naming the subproblem precisely enough that the recurrence falls out. Once you can say what dp[i] means in one sentence, the transition and the base case usually write themselves.

When it applies#

Two properties have to hold, and checking them takes ten seconds:

• Optimal substructure. The best answer for a problem can be assembled from the best answers to smaller versions of it. If the best way to make 6 can be built from the best way to make 3, you have it.
• Overlapping subproblems. The same smaller version comes up many times. Without this, caching buys nothing — you have plain divide and conquer, like merge sort, where the halves are all distinct.

The second one is what separates DP from backtracking. Backtracking enumerates every candidate because they are all different; DP notices that most branches are recomputing the same handful of answers and stops doing it.

Greedy sits on the other side. A greedy algorithm makes the locally best choice and never reconsiders — which is faster when it works, and silently wrong when it does not. The example below is exactly that case.

Filling the table#

Coin Change is the archetype: the fewest coins that add to a target, from an unlimited supply of given denominations.

Watch which earlier cells each new one is built from — the green ones — and notice they are always to the left, already final. That is what makes a single left-to-right pass sufficient.

The denominations are chosen to make a point. Greedy takes the largest coin that fits: 4, then 1, then 1, for three coins. The table finds 3 + 3, which is two. Greedy is wrong here, and no amount of tweaking the greedy rule fixes it — you have to consider every coin at every amount, which is what the inner loop does.

dp = array of size (amount + 1), filled with INFINITY
dp[0] = 0                            // base case: nothing costs no coins

for a = 1 .. amount:
    for c in coins:
        if c <= a and dp[a - c] != INFINITY:
            dp[a] = min(dp[a], dp[a - c] + 1)

return dp[amount] if reachable else -1

Note the sentinel. INFINITY means “not reachable”, and it has to be distinguishable from a real answer — initialising with 0 instead would make every amount look free. Choosing the right initial value is a real design decision, not boilerplate: 0 for counting problems, INFINITY for minimisation, -INFINITY for maximisation, false for reachability.

The five questions#

Every DP problem is the same five questions. Answer them in order, in words, before writing any code:

1. What is the subproblem? State dp[i] in one sentence. This is 80% of the work, and the sentence has to be exact — “the fewest coins for amount i”, not “something about coins”.
2. What is the transition? How dp[i] is built from smaller entries. If the sentence in step 1 was precise, this is usually obvious.
3. What is the base case? The smallest input, answered directly.
4. In what order? Every entry a transition reads must already be computed.
5. Where is the answer? Often dp[n], but not always — sometimes it is the maximum over the whole table, which is a different thing and a common slip.

If you get stuck, it is nearly always question 1, and the fix is nearly always to add a dimension. “The fewest coins for amount i” is one-dimensional; “can the first i items hit sum j” is two. When a recurrence refuses to close, the subproblem is usually missing a parameter.

Two directions, one recurrence#

Top-down is the brute-force recursion with a cache bolted on. Write the recursion first, confirm it is correct, then add three lines:

memo = empty map

function solve(state):
    if state in memo:  return memo[state]      // already computed
    if state is a base case:  return base value

    answer = combine(solve(smaller states))
    memo[state] = answer
    return answer

Bottom-up is the same recurrence as a loop, filling the table in dependency order — what the player above does. It avoids recursion depth limits, is usually faster by a constant factor, and makes space optimisation possible.

The practical advice: derive top-down, submit bottom-up if it matters. Going straight to a table means guessing the iteration order before you are sure of the recurrence, which is how people get stuck. Memoising a recursion you already believe is a mechanical step you can do under time pressure.

One genuine advantage top-down keeps: it only ever visits states that are actually reachable. A table computes every cell whether it is needed or not, which for sparse state spaces is wasted work.

The shapes worth knowing#

One dimension over an index. dp[i] depends on a fixed number of earlier entries. Climbing Stairs is dp[i] = dp[i-1] + dp[i-2], which is Fibonacci wearing a hat. Word Break is dp[i] = true if some j < i has dp[j] and the substring j..i is a word — the subproblem being “can the first i characters be segmented”, which is the sentence that makes the problem easy.

Maximum Subarray is the same family with an important twist: dp[i] is the best sum ending exactly at i, not the best sum in the first i elements. The answer is then the maximum over the whole array rather than the last cell. Because each entry only needs the one before it, the table collapses to a single variable — which is Kadane’s algorithm, stepped through line by line in the snippet. It is worth seeing that it is DP, not a trick.

Two dimensions over a grid. Unique Paths is dp[r][c] = dp[r-1][c] + dp[r][c-1], with the first row and column as the base case. Grid DP is the easiest family to picture and a good place to practise question 4, because the order is forced: you cannot compute a cell before the ones above and to its left.

Knapsack. Partition Equal Subset Sum is the classic in disguise — a set can be split into two equal halves exactly when some subset sums to half the total, so it is subset-sum, which is 0/1 knapsack with booleans. The subproblem is “using the first i numbers, can I make sum j”.

That family has one detail that catches nearly everyone, and it is worth stating plainly:

When the table is collapsed to one dimension, 0/1 knapsack iterates the capacity downwards and unbounded knapsack iterates it upwards.

The reason is direct. Going upwards, dp[j - x] has already been updated in this pass, so the item gets used again — which is what Coin Change wants and what subset-sum must not allow. Going downwards, dp[j - x] still holds the previous pass’s value, so each item is used at most once. Same three lines, opposite loop direction, completely different problem.

Substrings and intervals. Longest Palindromic Substring has a genuine DP formulation — dp[i][j] is whether s[i..j] is a palindrome, built from dp[i+1][j-1] — and it is O(n²) in both time and space. Expanding around each of the 2n - 1 centres gets the same O(n²) time in O(1) space and is less code. Knowing the DP exists is worth something; using it here is not.

Cutting the space#

Once the table works, look at what a transition actually reads. If dp[i] only needs dp[i-1] and dp[i-2], the array is doing nothing that two variables could not:

prev2, prev1 = base values

for i = 2 .. n:
    cur = f(prev1, prev2)
    prev2, prev1 = prev1, cur

The 2-D version is the same move: a grid DP that reads only the row above collapses to one row, taking O(n) space instead of O(n·m). This is a routine follow-up question, so it is worth being able to do on request — and worth not doing first, because the full table is easier to debug.

The cost of collapsing is that you throw away the information needed to reconstruct which choices produced the answer. If the problem wants the actual subset or path rather than its value, keep the table, and walk it backwards from the answer cell asking at each step which predecessor could have produced this value.

Complexity, and getting unstuck#

The cost is number of states × work per state, and saying it that way makes it easy. Coin Change has amount states and does len(coins) work at each, so O(amount × coins). Unique Paths has n × m states and O(1) work each. A DP over subsets has 2ⁿ states, which is why bitmask DP only appears when n is around 20.

When you are stuck, the reliable escape is always the same sequence:

1. Write the brute-force recursion, however slow. Do not think about efficiency yet.
2. Look at its parameters — those are the state, and that is question 1 answered for you.
3. Memoise it.
4. Convert to a table only if you need to.

That path works even when the insight does not arrive, which is why it is worth practising deliberately rather than reaching for a remembered recurrence.

What goes wrong#

• The array is one too short. A dp over amounts 0..n needs n + 1 entries. Almost every DP off-by-one is this.
• The wrong initial value, so unreachable states look reachable, or a maximum starts above every real answer.
• The wrong loop direction in a collapsed knapsack, which turns 0/1 into unbounded without any error.
• The answer is not dp[n]. For “best ending exactly here” formulations it is the maximum over the table.
• The state is incomplete. If the recurrence needs to know something the parameters do not carry, no amount of caching helps — add the dimension.

Recognising it#

Reach for DP when:

• The question asks for a count, a maximum, a minimum, or whether something is possible — rather than for a list of every arrangement, which is backtracking.
• The obvious recursion branches and revisits the same inputs.
• You can see a sequence of decisions where each one leaves a smaller version of the same problem behind.
• The constraints are too large for exponential but the state space is small — n up to 10⁴ or so with a one-dimensional state is a strong hint.

And the negative check worth doing: if a simple greedy rule provably works, use it — it is faster and shorter. DP is what you fall back to when you cannot prove the greedy choice is safe. The coins above are the standing reminder that “seems reasonable” is not a proof.

Summary#

Name the subproblem in one exact sentence and most of the difficulty goes with it; the transition, the base case, and the order all follow from that sentence. Derive it as a recursion, memoise it, and turn it into a table only if you need the speed or the space. The recurring judgement calls are few: what the sentinel should be, which direction the loop runs, and whether the answer is the last cell or the best cell. Everything else is bookkeeping.