Dynamic programming: the basics

You’ll recognise it when

• The question asks for the best value (max, min) or how many ways, not for one specific arrangement.
• You make a sequence of choices (take or skip, one step or two, which coin), and each choice limits the next ones.
• A recursive solution is easy to write but slow, and printing its calls shows the same arguments again and again.
• The input is small in one dimension you can index by: a position, an amount, a length.

It’s often confused with greedy, which commits to whatever looks best right now; DP keeps the best answer for every subproblem, so a choice that looks bad now can still win later.

The idea

A street of houses, each with some money inside. You want as much as possible, but robbing two neighbours sets off the alarm. Walk down the street and, at each door, write one number on a notepad: the most you could have taken from the houses so far. At the next door you don’t replan the whole street. You look at the last two numbers on the pad and decide.

That’s dynamic programming: solve each subproblem once, write the answer down, and build bigger answers from smaller ones. It starts from a plain recursive idea. For the last house i there are only two options:

• Skip it. The best is whatever houses 0 to i - 1 can give.
• Rob it. Then house i - 1 is off limits, so you get money[i] plus the best from houses 0 to i - 2.

def best(i):                  # most money from houses 0..i
    if i < 0:
        return 0
    return max(best(i - 1), best(i - 2) + money[i])

That’s correct, but slow. best(9) calls best(8) and best(7); best(8) calls best(7) again, and so on. The number of calls grows like the Fibonacci numbers, about 1.6ⁿ: a street of 60 houses needs over a trillion calls. Yet there are only n different questions. Memoization stores each answer the first time it’s computed, and every later call is a lookup:

from functools import cache

@cache
def best(i):
    if i < 0:
        return 0
    return max(best(i - 1), best(i - 2) + money[i])

Now each best(i) runs once: O(n). The bottom-up version below goes one step further and fills the answers in a loop, in an order where everything a cell needs is already there. Every DP answers the same five questions:

How it works

We fill dp from left to right, and at each house compare the two options.

Scroll through the steps and the graphic follows along. You can also step with the arrow keys, turn on quiz me to decide each house yourself, or edit the amounts.

Why it’s correct: every legal plan for houses 0 to i either skips house i or robs it. A best plan that skips it is a best plan for houses 0 to i - 1, which is dp[i-1]. A best plan that robs it can’t use house i - 1, and the rest of it may as well be the best plan for houses 0 to i - 2, since swapping in a better one would only help. So max(skip, take) covers every case, and filling left to right means both are known when we need them.

def rob(money):
    """Most money you can take without robbing two neighbouring houses."""
    n = len(money)
    if n == 0:
        return 0
    # dp[i] = the best total using houses 0..i only
    dp = [0] * n
    dp[0] = money[0]
    for i in range(1, n):
        skip = dp[i - 1]
        take = (dp[i - 2] if i >= 2 else 0) + money[i]
        dp[i] = max(skip, take)
    return dp[n - 1]

#include <vector>
#include <algorithm>
using namespace std;

// Most money you can take without robbing two neighbouring houses.
long long rob(const vector<long long>& money) {
    int n = money.size();
    if (n == 0) return 0;
    // dp[i] = the best total using houses 0..i only
    vector<long long> dp(n);
    dp[0] = money[0];
    for (int i = 1; i < n; i++) {
        long long skip = dp[i - 1];
        long long take = (i >= 2 ? dp[i - 2] : 0) + money[i];
        dp[i] = max(skip, take);
    }
    return dp[n - 1];
}

class HouseRobber {
    // Most money you can take without robbing two neighbouring houses.
    static long rob(long[] money) {
        int n = money.length;
        if (n == 0) return 0;
        // dp[i] = the best total using houses 0..i only
        long[] dp = new long[n];
        dp[0] = money[0];
        for (int i = 1; i < n; i++) {
            long skip = dp[i - 1];
            long take = (i >= 2 ? dp[i - 2] : 0) + money[i];
            dp[i] = Math.max(skip, take);
        }
        return dp[n - 1];
    }
}

Each cell looks back only two places, so you can keep just those two numbers instead of the whole array. This is the O(1)-space version; the tuple assignment matters, because the new value must be computed from the old pair:

def rob(money):
    prev2 = prev1 = 0            # dp[i-2] and dp[i-1]
    for x in money:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Why it’s O(n)

There are n states, and each is filled with one comparison of two numbers already in the table: O(n) time. The table takes O(n) space; the rolling version keeps two numbers, O(1).

The general rule for DP is number of states × work per state. Plain recursion pays for every path through the choices instead of every state, which is what makes it exponential:

Common mistakes

max(sum(money[0::2]), sum(money[1::2]))   # ✗ 8 on [6, 1, 2, 7]
max(dp[i-1], dp[i-2] + money[i])          # ✓ 13

take = dp[i - 2] + money[i]                    # ✗ dp[-1] when i == 1
take = (dp[i - 2] if i >= 2 else 0) + money[i] # ✓

prev2 = prev1; prev1 = max(prev1, prev2 + x)   # ✗ uses the new prev2
prev2, prev1 = prev1, max(prev1, prev2 + x)    # ✓ both from the old pair

Variations

• Top-down (memoized). Write the recursion, add a cache, done. It’s the fastest to get right and only computes the states it actually reaches; the price is recursion depth and a little overhead per call.
• Climbing stairs and Fibonacci. The number of ways to climb n steps taking 1 or 2 at a time is ways[n] = ways[n-1] + ways[n-2]: the same shape as House Robber with + instead of max.
• Circular street. If the first and last houses are neighbours, they can’t both be robbed. Solve twice, once without the first house and once without the last, and take the larger.
• Reconstructing the choice. The table answers “how much”; to answer “which houses”, walk back from the end as in the last step, or store the winning choice for each cell while filling it.
• Spotting DP in general. Ask the five questions: what’s the state, what’s the choice, how does the answer follow from smaller states, what are the base cases, and in what order can you fill them. If plain recursion repeats arguments, the answers to those questions are your solution.