Dynamic Programming

PHASE 1: The Architectural Blueprint

PHASE 2: The Implementation Journey

Once the logic is clear, we move from a slow, "forgetful" recursion to an optimized, "remembering" table.

Imagine a chain where each link's strength (its value) depends directly on the strength of a few preceding links. You build this chain one link at a time, moving forward, knowing that to determine the strength of the current link, you only need to look back a fixed number of steps.

The state for linear DP is typically one-dimensional, represented as dp[i]. This dp[i] signifies the optimal answer for a prefix of the input of size i, or the optimal result ending at index i. The key is that i is usually a direct index in the problem's input array or sequence.

To calculate dp[i], you look back at a fixed, small number of previous states, like dp[i-1], dp[i-2], or dp[i-k]. The transition function combines these previous results to determine the current state. There's no branching or complex choices; it's a straightforward progression. For example, dp[i] = dp[i-1] + dp[i-2] (Fibonacci), or dp[i] = max(dp[i-1], dp[i-2]).

1. Identify Base Cases: Determine the values for the smallest possible i (e.g., dp[0], dp[1]).
2. Initialize DP Array: Create an array (or memoization table) to store results.
3. Iterate Forward: Use a loop starting from the first calculated state up to the target state.
4. Apply Recurrence: Inside the loop, compute dp[i] using the defined recurrence relation, referencing already computed dp[j] where j < i.

Given n stairs, you can climb either 1 or 2 steps at a time. In how many distinct ways can you climb to the top?

Imagine you're at a crossroads with each item you encounter. You can either pick it up (if you have the capacity) or leave it behind. Your goal is to make these binary decisions for all items to maximize some value without exceeding a global limit.

The state typically involves two dimensions: dp[i][capacity].
- i usually represents the current item being considered (or the number of items processed so far).
- capacity represents the remaining capacity or budget.
dp[i][capacity] stores the optimal value (or count, etc.) achievable when considering the first i items with the given capacity.

At each state dp[i][capacity], you face a binary choice for the i-th item:
1. Don't Take: The value comes from the previous state where the i-th item was not considered: dp[i-1][capacity].
2. Take: If the i-th item fits (weight[i] <= capacity), the value is the item's value plus the optimal value from the state before it was taken: value[i] + dp[i-1][capacity - weight[i]].
The transition is then dp[i][capacity] = max(Don't Take, Take).

1. Identify Base Cases: Usually, dp[0][...] (no items) or dp[...][0] (zero capacity) are initialized to 0.
2. Initialize DP Table: Create a 2D array dp[N+1][W+1].
3. Iterate: Use nested loops: outer loop for items (i) and inner loop for capacities (w).
4. Apply Recurrence: Inside the loops, compute dp[i][w] using the "take or not take" logic, referencing dp[i-1][...] values.

Given items with weights and values, and a knapsack with a maximum capacity, determine the maximum value you can put into the knapsack. Each item can only be included once.

i=1 (item 0: v=6, w=2):
- w=0,1: dp[1][w] = dp[0][w] = 0 (cannot take)
- w=2: dp[1][2] = max(dp[0][2], 6 + dp[0][0]) = max(0, 6+0) = 6
- w=3,4,5: dp[1][w] = max(dp[0][w], 6 + dp[0][w-2]) = 6

i=2 (item 1: v=10, w=3):
- w=0,1: dp[2][w] = dp[1][w] = 0
- w=2: dp[2][2] = max(dp[1][2], 10 + dp[1][-1]) = dp[1][2] = 6 (cannot take item 1)
- w=3: dp[2][3] = max(dp[1][3], 10 + dp[1][0]) = max(6, 10+0) = 10
- w=5: dp[2][5] = max(dp[1][5], 10 + dp[1][2]) = max(6, 10+6) = 16
Final answer: dp[2][5] = 16

Imagine a vending machine with infinite stock of each item. You want to reach a target value, and you can pick any item from the menu as many times as you like. The challenge is to find the optimal way to reach that target.

The state is typically one-dimensional: dp[target]. This dp[target] represents the optimal answer (e.g., minimum coins, maximum ways) to achieve the exact target value using any combination of the available items.

To calculate dp[target], you iterate through each available item. For each item c, if target - c is a valid previous state, you consider using item c to reach target. The transition typically looks like:
dp[target] = min(dp[target], 1 + dp[target - c]) (for minimum count)
or
dp[target] = dp[target] + dp[target - c] (for total ways)

The crucial difference from "Take/Not Take" is that when you "take" an item, you can potentially take it again from the new reduced target.

1. Identify Base Cases: dp[0] is often 0 (0 coins for 0 amount, 1 way to make 0 sum).
2. Initialize DP Array: Create a 1D array dp[Target+1], often initialized to infinity (for minimization) or 0 (for counting ways, except dp[0]).
3. Iterate: Use nested loops: outer loop for the target (from 1 up to the total target) and an inner loop for each available item. This order ensures that each dp[i] is computed using all possible items.
4. Apply Recurrence: Inside the loops, update dp[target] based on the values of dp[target - item].

Given an array of coin denominations and a total amount, find the fewest number of coins that you need to make up that amount. You have an infinite supply of each coin.

amt = 1:
- coin 1: dp[1] = min(Inf, 1 + dp[0]) = 1
amt = 2:
- coin 1: dp[2] = min(Inf, 1 + dp[1]) = 2
- coin 2: dp[2] = min(2, 1 + dp[0]) = 1
amt = 3:
- coin 1: dp[3] = min(Inf, 1 + dp[2]) = 1 + 1 = 2 (using coin 2, then coin 1)
- coin 2: dp[3] = min(2, 1 + dp[1]) = min(2, 1 + 1) = 2
amt = 4:
- coin 1: dp[4] = min(Inf, 1 + dp[3]) = 1 + 2 = 3
- coin 2: dp[4] = min(3, 1 + dp[2]) = min(3, 1 + 1) = 2
- coin 5: (skip)
amt = 5:
- coin 1: dp[5] = min(Inf, 1 + dp[4]) = 1 + 2 = 3
- coin 2: dp[5] = min(3, 1 + dp[3]) = min(3, 1 + 2) = 3
- coin 5: dp[5] = min(3, 1 + dp[0]) = min(3, 1 + 0) = 1
Final answer: dp[5] = 1

Imagine you have two sequences, like two strings, and you want to compare them or find common patterns. You use a 2D grid where each cell (i, j) represents the result of comparing the prefix of the first sequence up to index i, with the prefix of the second sequence up to index j. The decisions involve matching, skipping, or aligning elements from either sequence.

The state is typically two-dimensional: dp[i][j].
- i represents the length of the prefix considered from the first sequence (or index in 0-based).
- j represents the length of the prefix considered from the second sequence (or index in 0-based).
dp[i][j] stores the optimal result (e.g., length of common subsequence, minimum edit distance) for these two prefixes.

To compute dp[i][j], you usually consider three possibilities, corresponding to how you 'matched' or 'aligned' the i-th element of the first sequence and the j-th element of the second:
1. Match: If sequence1[i-1] == sequence2[j-1], then dp[i][j] might depend on dp[i-1][j-1] (matching both).
2. Skip from Sequence 1: dp[i][j] might depend on dp[i-1][j] (ignoring current element of sequence 1).
3. Skip from Sequence 2: dp[i][j] might depend on dp[i][j-1] (ignoring current element of sequence 2).
The transition combines these, often taking the max or min of these options.

1. Identify Base Cases: The first row (dp[0][j]) and first column (dp[i][0]) represent the scenario where one of the input sequences is empty. Initialize these with values that reflect the cost or value of matching against an empty prefix (e.g., 0 for commonalities, or the current index for edit operations).
2. Initialize DP Table: Create a 2D array dp[N+1][M+1], where N and M are the lengths of the sequences.
3. Iterate: Use nested loops, typically from i=1 to N and j=1 to M.
4. Apply Recurrence: Inside the loops, compute dp[i][j] using the transition logic based on whether sequence1[i-1] and sequence2[j-1] match.

Given two strings, find the length of their longest common subsequence. A subsequence is formed by deleting zero or more characters from a string.

i=1 (char 'A'):
- j=1 (char 'A'): text1[0]=='A', text2[0]=='A'. Match! dp[1][1] = 1 + dp[0][0] = 1.
- j=2 (char 'B'): No match. dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1.
- ... and so on.
If text1[i-1] == text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

After filling the table, dp[text1.length][text2.length] holds the answer.
For "ACE", "ABCDE", LCS is "ACE", length 3.
dp[3][5] would be 3.

The robot only moves right or down, so it can never revisit a cell and never go backwards. Every path is just a sequence of moves, and we want to count them.

Notice what the movement rule buys us. Because the robot only moves right or down, a cell can only be reached from the cell above it or the cell to its left. Two ways in — and we build everything on exactly that.

Stand on any cell (r, c) and ask how the robot got there. Its last move was either a step down (so it was at (r-1, c)) or a step right (so it was at (r, c-1)). No third option, and the two cases never overlap, because a path's last move is a single definite thing.

So the number of paths ending at (r, c) is the number ending at the cell above plus the number ending at the cell to the left.

f(r, c) = f(r-1, c) + f(r, c-1)

Base cases come from the edges. Any cell in the top row can only be reached by walking straight right from the start — there is no row above to come from — so there is exactly 1 path to each of them. Likewise any cell in the leftmost column has exactly 1 path. And f(0, 0) = 1, the empty path: the robot is already there.

Because we are counting, we add the two branches. (A min or max would be for a best-value question; here we just want how many.)

Plain recursion first:

def unique_paths(m, n):
    def f(r, c):
        if r == 0 or c == 0: return 1        # top row or left column: one way
        return f(r - 1, c) + f(r, c - 1)
    return f(m - 1, n - 1)

Two branches per call and a depth of about m + n, so this is exponential — while there are only m × n genuinely different cells. Almost every cell in the middle is recomputed from many different directions. Memoise it:

def unique_paths(m, n):
    memo = {}
    def f(r, c):
        if r == 0 or c == 0: return 1
        if (r, c) in memo: return memo[(r, c)]
        memo[(r, c)] = f(r - 1, c) + f(r, c - 1)
        return memo[(r, c)]
    return f(m - 1, n - 1)

m × n states, constant work each: O(M × N).

Now build a table instead of recursing. Let dp[r][c] hold what f(r, c) returned — the number of paths to cell (r, c). Swap the calls for array reads and the recurrence becomes:

dp[r][c] = dp[r-1][c] + dp[r][c-1]

dp[r][c] needs the cell above and the cell to the left, both at smaller indices. So fill the grid top-to-bottom, left-to-right, and both are ready when you reach (r, c). The base cases copy straight from the recursion: it returned 1 whenever r == 0 or c == 0, so the whole top row and left column start at 1. The loops then begin at (1, 1), and the answer is dp[m-1][n-1]:

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]     # top row and left column start at 1
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

Initialising the whole grid to 1 quietly handles both base cases at once, since the loops never touch row 0 or column 0.

When you compute row r left to right, the value you need from above is dp[r-1][c], and the value you need from the left is dp[r][c-1] — which you just computed on this same row. So a single array works, if you read it at the right moment:

def unique_paths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] = row[c] + row[c - 1]
            #        ^above    ^left (already updated this row)
    return row[n - 1]

The trick is that row[c] still holds the previous row's value at the instant you read it, and row[c-1] already holds this row's — so one array plays both parts. This overlapping-read pattern shows up in every grid problem where a cell depends on up and left, so it is worth staring at until it feels obvious.

1  1  1
1  ?  ?
1  ?  ?

1  1  1
1  2  3
1  3  6

Answer 6. Check it by hand: the robot makes 2 downs and 2 rights in some order, and the distinct orderings of DDRR are DDRR, DRDR, DRRD, RDDR, RDRD, RRDD — six.

That hand-check hints at something. Every path from corner to corner makes exactly m-1 downward moves and n-1 rightward moves, in some order — always the same counts, no matter the route. So a path is completely described by which of the m+n-2 moves are the downward ones. The number of ways to choose that is the binomial coefficient:

C(m + n - 2, m - 1)

For a 3 × 7 grid that is C(8, 2) = 28, matching the table. This closes the problem in O(min(m, n)) time with no table at all, and it is worth mentioning in an interview — it shows you saw the structure rather than just applying machinery.

But be honest about its limits. The formula works only because the grid is empty and every route is legal. Put a single obstacle in the way and the counting argument collapses, because paths are no longer interchangeable. The table survives that change with a one-line edit. The general lesson: a closed-form shortcut is usually more fragile than the table that produced it, so know both and know which assumption each one leans on.

Pick a day to buy and a strictly later day to sell, and maximise sell price − buy price. You may also decline to trade at all, which is why the floor is 0 rather than a negative number. On a strictly falling market like [7, 6, 4, 3, 1], every possible trade loses money, so the answer is 0.

Note carefully: this is not "biggest number minus smallest number". On [2, 9, 1] the smallest is 1 and the largest is 9, but the 9 comes before the 1, so that pair is not a legal trade. The best legal trade is buy at 2 and sell at 9, for 7. Order is part of the constraint, and every wrong solution to this problem ignores it in some way.

Try every pair of days with the buy first:

def max_profit(prices):
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            best = max(best, prices[j] - prices[i])
    return best

Count it: day 0 is compared against n-1 later days, day 1 against n-2, and so on, giving about N²/2 comparisons. With prices up to 100000 days, that is five billion — far too slow.

It is slow because it treats every pair as its own puzzle. But the real decision is per day: on each day I either own the share or I do not, and that alone decides what I can do next. Walk the days once, tracking that, and the pairs take care of themselves.

Walk the days one at a time. Standing on day i, I am in one of two situations:

So besides the day, the thing that decides my options is: am I holding the share?

What can I do on day i?

The single-trade rule lives in one place: selling ends the trade (it never loops back to buy again), and buying starts from zero.

Base case: past the last day (i == n) there is nothing left to earn, so f = 0. The answer is f(0, not holding).

Write the story down exactly. holding is a boolean:

def max_profit(prices):
    n = len(prices)

    def f(i, holding):
        if i == n: return 0
        if holding:
            return max(prices[i], f(i + 1, True))        # sell (trade done), or keep
        else:
            return max(-prices[i] + f(i + 1, True),      # buy today
                       f(i + 1, False))                  # wait

    return f(0, False)

Correct, but exponential — each day branches in two. Yet there are only n × 2 different (i, holding) questions, so memoise: solve each once, reuse after.

def max_profit(prices):
    n = len(prices)
    memo = {}

    def f(i, holding):
        if i == n: return 0
        if (i, holding) in memo: return memo[(i, holding)]
        if holding:
            best = max(prices[i], f(i + 1, True))
        else:
            best = max(-prices[i] + f(i + 1, True), f(i + 1, False))
        memo[(i, holding)] = best
        return best

    return f(0, False)

O(N) time and space.

Turn it into a table. Let dp[i][h] hold what f(i, h) returned. Each recurrence line becomes an array assignment. Every read is from day i+1, so fill from the last day backwards, starting with day n all zeros. The answer is dp[0][0]:

def max_profit(prices):
    n = len(prices)
    dp = [[0, 0] for _ in range(n + 1)]      # dp[i][0] = not holding, dp[i][1] = holding

    for i in range(n - 1, -1, -1):
        dp[i][1] = max(prices[i], dp[i + 1][1])                    # holding: sell or keep
        dp[i][0] = max(-prices[i] + dp[i + 1][1], dp[i + 1][0])    # empty: buy or wait

    return dp[0][0]

Each day reads only day i+1, so two variables replace the whole table:

def max_profit(prices):
    next_hold, next_free = 0, 0             # dp[i+1][1], dp[i+1][0]
    for p in reversed(prices):
        hold = max(p, next_hold)                    # sell today, or keep
        free = max(-p + next_hold, next_free)       # buy today, or wait
        next_hold, next_free = hold, free
    return next_free

O(N) time, O(1) space.

Answer free = 5, buying at 1 and selling at 6.

And the falling market [7, 6, 4, 3, 1]: every buy costs more than any later sell, free never rises above 0, and the answer is 0 — we decline to trade.

The move that solved this is the one to keep: when the day alone is not enough, ask what decides your options and add exactly that to the state. Here it was a single yes/no — am I holding the share? — and everything else followed the usual ladder: write the recursion straight from the two cases, memoise it, turn it into a table, then trim to two variables.

That two-state view is what carries into the harder variants. The rest of this family — cooldowns, fees, at most k transactions — keeps the same skeleton and only grows the state. Learn this version properly and the rest is bookkeeping.

A subsequence keeps the original order but allows gaps. In [10, 9, 2, 5, 3, 7, 101, 18], the elements 2, 5, 7, 101 appear in that order — not next to each other, but never out of order — so [2, 5, 7, 101] is an increasing subsequence of length 4.

Strictly increasing means each element must be larger than the one before, so [7, 7, 7] has a longest increasing subsequence of length 1, not 3. That word is worth confirming out loud with an interviewer, because the non-strict version needs a different comparison in exactly one place and is otherwise identical.

Brute force is to generate all 2ⁿ subsequences and check each. For 2500 elements that number has 750 digits, so we need real structure.

The first instinct is to define f(i) as "the length of the longest increasing subsequence within the first i elements". It sounds right and it is useless. Suppose f(5) = 3 — you know a length-3 subsequence exists somewhere in that prefix, but you have no idea what its last value is, and that is precisely what you need in order to decide whether nums[5] can be appended to it.

Two prefixes with the same best length can end on very different values, and those futures differ. So that state is no good — a state must decide what can happen next, and this one does not.

The price of this definition is that f(i) is no longer the answer for the prefix; it is a local fact. The overall answer becomes the maximum of f(i) over all i, because every increasing subsequence ends somewhere, and whichever index that is will have recorded it.

What can come before nums[i] in a subsequence ending at i? Any earlier element that is strictly smaller. If we choose j < i with nums[j] < nums[i], then the best we can do is the best subsequence ending at j, plus this one element:

f(i) = 1 + max( f(j) for all j < i with nums[j] < nums[i] )

and if no such j exists, f(i) = 1 — the element standing alone.

def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n                       # every element is a subsequence of length 1
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Count the cost: index i scans i earlier elements, so the total is about N²/2 — around three million operations at the maximum size, which is comfortably fast enough. This version is worth being able to write instantly, because it generalises to almost every variant.

Note the loops read only smaller indices, so the natural left-to-right order is already correct, and the base case dp[i] = 1 is folded into the initialisation.

dp = [1, 1, 1, 2, 2, 3, 4, 4], and the answer is max(dp) = 4.

Look at where the maximum lives: at indices 6 and 7, not at the end. This is exactly why the answer is a maximum over the table rather than its last entry.

There is an O(N log N) solution, and it is worth learning properly rather than memorising, because the reasoning is beautiful and the code is four lines.

Keep an array tails, where tails[k] holds the smallest possible value that any increasing subsequence of length k+1 could end with, considering everything processed so far.

Why do we want the smallest ending? Because a smaller ending is strictly more useful — anything that can be appended to a subsequence ending in 9 can also be appended to one ending in 3, but not the other way round. Among all subsequences of a given length, the one with the smallest tail dominates all the others, so it is the only one worth remembering.

For each new value x:

from bisect import bisect_left

def length_of_lis(nums):
    tails = []
    for x in nums:
        pos = bisect_left(tails, x)        # leftmost index with tails[pos] >= x
        if pos == len(tails):
            tails.append(x)                # x extends the longest run
        else:
            tails[pos] = x                 # x improves an existing length
    return len(tails)

Two facts make this work, and both deserve a moment.

tails is always sorted. A subsequence of length 3 contains, inside it, a subsequence of length 2 ending at a strictly smaller value, so the best length-2 tail can only be smaller than the best length-3 tail. Sortedness is what lets us binary-search, which is where the log N comes from.

Overwriting never breaks anything. Replacing tails[pos] does not destroy a subsequence we might still need, because the length recorded at that position is unchanged and its ending only got smaller — strictly more permissive going forward.

For strictly increasing we use bisect_left; for the non-decreasing variant, where equal values are allowed, use bisect_right. That single character is the whole difference.

The recognition signal is broader than "increasing numbers". Reach for this whenever a problem asks for the longest chain of items where each one must beat the previous one on some ordering, and items may be skipped.

Concretely: stacking boxes that must fit inside one another, chains of pairs, scheduling non-overlapping intervals — many of these reduce to this shape after a sort, or to its mirror image. A two-dimensional version, where each item must beat the previous one on two keys at once, becomes exactly this once you sort on one key and run the chain on the other.

Two portable lessons to keep:

When a state does not determine the future, add whatever is missing — often "what does it end with?" — and accept that the answer becomes an aggregate over the table rather than one cell.

When you keep a set of candidates, ask whether some of them dominate others. Here, among all subsequences of a given length, only the one with the smallest tail could ever matter. Throwing away dominated candidates is what collapsed a quadratic scan into a binary search, and the same move appears all over algorithm design.

Multiplying a p × q matrix by a q × r matrix takes p × q × r scalar multiplications — one for each cell of the p × r result, times the q terms summed into it. The order of the matrices in the chain is fixed and cannot be shuffled, but because matrix multiplication is associative, you may choose where the parentheses go, and different groupings cost wildly different amounts while producing the identical result.

Take three matrices A (1 × 2), B (2 × 3), C (3 × 4).

Nearly twice the work for the same answer. On longer chains the gap becomes enormous, which is why compilers and numerical libraries genuinely solve this problem.

The dimensions are given as a single array because adjacent matrices must agree: if matrix i is dims[i-1] × dims[i], then matrix i+1 starts with dims[i] rows automatically. One array of n+1 numbers encodes n matrices with no possibility of a mismatch.

"Always multiply the cheapest adjacent pair first" seems reasonable. It is wrong, because the cheap multiplication you perform now leaves behind a result matrix whose shape determines the cost of everything afterwards. A cheap step can leave a fat matrix that poisons the rest of the chain, and an expensive step can leave a thin one that makes everything after it cheap.

Enumerating every parenthesisation is not an option either — the number of ways to bracket n matrices is the Catalan number, which grows roughly like 4ⁿ. For 99 matrices that is beyond astronomical.

Here is the trick. The other problems walked along one element at a time, but a chain has no natural "next" — the grouping is a tree, not a walk. So instead of the first step, I think about the last one.

Say I want to multiply matrices i through j. However I bracket them, there is exactly one multiplication I do last, and it joins a left block with a right block. That last step splits the chain at some k: matrices i..k are already collapsed into one matrix, matrices k+1..j into another, and I multiply those two.

I don't know the best k, so I try every split from i to j-1, solve each side the same way, and keep the cheapest.

Why can the two sides be solved separately? Because their shapes are fixed no matter how each is bracketed inside: block i..k is dims[i-1] × dims[k], block k+1..j is dims[k] × dims[j]. So the final multiply always costs dims[i-1] × dims[k] × dims[j], and the two sub-costs simply add.

f(i, j) = min over k from i to j-1 of [ f(i, k) + f(k+1, j) + dims[i-1] × dims[k] × dims[j] ]

Base case: f(i, i) = 0 — a single matrix needs no multiplication. The answer is f(1, n).

Write the story down as plain recursion — it simply tries every split:

def matrix_chain(dims):
    n = len(dims) - 1              # number of matrices

    def f(i, j):
        if i == j: return 0                       # single matrix: nothing to do
        best = float('inf')
        for k in range(i, j):                     # last multiplication splits after k
            cost = f(i, k) + f(k + 1, j) + dims[i - 1] * dims[k] * dims[j]
            best = min(best, cost)
        return best

    return f(1, n)

Correct, but it re-solves the same intervals again and again — the number of bracketings is Catalan-many, roughly 4ⁿ. Yet there are only about N²/2 different (i, j) intervals. So keep a notebook and solve each once:

def matrix_chain(dims):
    n = len(dims) - 1
    memo = {}

    def f(i, j):
        if i == j: return 0
        if (i, j) in memo: return memo[(i, j)]
        best = float('inf')
        for k in range(i, j):
            cost = f(i, k) + f(k + 1, j) + dims[i - 1] * dims[k] * dims[j]
            best = min(best, cost)
        memo[(i, j)] = best
        return best

    return f(1, n)

Turn it into a table. Let dp[i][j] hold what f(i, j) returned, and swap each call for an array read:

dp[i][j] = min over k of [ dp[i][k] + dp[k+1][j] + dims[i-1] × dims[k] × dims[j] ]

Now the fill order — and this is where interval problems differ. dp[i][j] reads dp[i][k] and dp[k+1][j], both covering shorter stretches of the chain, but one has a larger i and the other a smaller j. Neither index moves consistently, so no plain ascending or descending loop works. What always shrinks, though, is the interval length. So loop by length, shortest first — then every sub-interval a cell needs is already filled. The base case dp[i][i] = 0 is the length-1 diagonal, and the answer is dp[1][n]:

def matrix_chain(dims):
    n = len(dims) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]     # dp[i][i] = 0 already

    for length in range(2, n + 1):                 # chains of 2, then 3, ...
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = (dp[i][k] + dp[k + 1][j]
                        + dims[i - 1] * dims[k] * dims[j])
                dp[i][j] = min(dp[i][j], cost)

    return dp[1][n]

Length 2:
- f(1,2) — only split k = 1: 0 + 0 + (1 × 2 × 3) = 6
- f(2,3) — only split k = 2: 0 + 0 + (2 × 3 × 4) = 24

Length 3:
- f(1,3), two splits to try:
- k = 1, meaning A(BC): f(1,1) + f(2,3) + 1 × 2 × 4 = 0 + 24 + 8 = 32
- k = 2, meaning (AB)C: f(1,2) + f(3,3) + 1 × 3 × 4 = 6 + 0 + 12 = 18

Answer 18, matching the hand calculation at the top of the page. And notice that the winning split reused f(1,2) = 6, computed once and consulted here — the whole reason for the table.

A longer one, dims = [40, 20, 30, 10, 30]: the table works up through lengths 2 and 3 and settles at 26000, against 120000 for the worst bracketing. The best grouping multiplies the middle pair down to a thin 20 × 10 matrix first, so that the expensive outer dimensions are only ever combined through a small shared dimension.

This is a different animal from everything earlier in the section, and recognising it is what matters.

The signal: the answer for a stretch of the input is built from the answers for two adjacent sub-stretches, and you get to choose where they meet. The input is a sequence, but the solution is a tree of pairings rather than a walk from one end to the other.

The state: an interval (i, j) — a left and a right boundary — rather than a single position.

The choice: the split point k inside the interval, tried exhaustively.

The loop order: by interval length, shortest first.

The typical cost: O(N³), from N² intervals times N split points.

The step that takes practice is finding the right thing to fix. Here we fixed the last multiplication, and that worked because it left two independent blocks whose shapes were already known. Fixing the first multiplication instead would have been a disaster — after multiplying one adjacent pair, the chain changes shape and the remaining problem is no longer a clean sub-interval of the original. When you set up an interval table, always ask: what can I fix so that what remains falls into independent pieces of the same kind?

Others in this family use the same skeleton with a different combining rule: the longest palindromic subsequence, minimum insertions to make a palindrome, optimal binary search trees, and scoring games where two players take from the ends of a row. Whenever the input is a sequence but the solution is a tree of pairings, reach for an interval (i, j) state and try every split inside it.

Start at city 0, visit every other city exactly once, come back. Minimise the total distance. Simple to state, and one of the most studied hard problems in computing — no method is known that solves it in polynomial time, and finding one would settle the biggest open question in the field.

So the goal here is not a fast solution; it is the best exponential solution, which turns a factorial into something merely exponential. With n ≤ 20, that difference is the difference between impossible and instant.

Note the costs may be asymmetric — going from A to B need not cost the same as B to A — so you cannot assume any symmetry to save work.

Fix city 0 as the start. Then a tour is an ordering of the other n-1 cities, so there are (n-1)! tours. For n = 20 that is 19!, roughly 1.2 × 10¹⁷. At a billion tours per second, several years.

Where is the waste? Consider two different partial tours: 0 → 3 → 5 → 2 and 0 → 5 → 3 → 2. They took different routes, but they have visited exactly the same set of cities and they are both standing in city 2. From here on, the cheapest way to finish is identical for both — the future does not care in what order the past happened, only which cities are used up and where you are now.

Brute force recomputes that shared future separately for every ordering that reaches the same situation. That is enormous duplication, and it is exactly the opening these tables exploit.

State Definition: f(mask, city) is the minimum cost to start at city, visit every city not yet in mask, and return to city 0 — where mask records the set of cities already visited.

The new idea is how to hold a set in a table index. A subset of at most 20 cities can be written as a 20-bit binary number: bit i is 1 if city i has been visited and 0 if not. That is a bitmask, and it is just an integer, so it can index an array directly.

The operations you need are three, and each is one instruction:

With n = 20 there are 2²⁰ ≈ one million possible masks and 20 possible current cities, giving about 20 million states. Each state tries up to 20 next cities, so roughly 400 million simple operations — heavy but feasible, and unimaginably better than 10¹⁷.

The recurrence is the natural one: from the current city, try every unvisited city as the next stop.

f(mask, city) = min over unvisited next of [ dist[city][next] + f(mask | (1 << next), next) ]

Base case: when mask contains every city, the tour is complete and only the trip home remains, so f = dist[city][0].

The answer is f(1, 0) — mask 1 means only city 0 has been visited, and we are standing in city 0.

def tsp(dist):
    n = len(dist)
    FULL = (1 << n) - 1                 # every city visited
    INF = float('inf')
    memo = {}

    def f(mask, city):
        if mask == FULL:
            return dist[city][0]                    # go home
        if (mask, city) in memo: return memo[(mask, city)]

        best = INF
        for nxt in range(n):
            if mask & (1 << nxt):                   # already visited
                continue
            cost = dist[city][nxt] + f(mask | (1 << nxt), nxt)
            best = min(best, cost)

        memo[(mask, city)] = best
        return best

    return f(1, 0)                                  # start in city 0, only it visited

The bottom-up version fills masks in decreasing order, because f(mask, ...) depends on masks with strictly more bits set — and adding a bit always makes the integer larger:

def tsp(dist):
    n = len(dist)
    FULL = (1 << n) - 1
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]

    for city in range(n):
        dp[FULL][city] = dist[city][0]              # base case: everything visited

    for mask in range(FULL - 1, 0, -1):
        for city in range(n):
            if not (mask & (1 << city)):            # we must be standing somewhere visited
                continue
            best = INF
            for nxt in range(n):
                if mask & (1 << nxt):
                    continue
                nxt_cost = dp[mask | (1 << nxt)][nxt]
                if nxt_cost != INF:
                    best = min(best, dist[city][nxt] + nxt_cost)
            dp[mask][city] = best

    return dp[1][0]

dist = [[ 0, 10, 15, 20],
        [10,  0, 35, 25],
        [15, 35,  0, 30],
        [20, 25, 30,  0]]

Only three orderings of cities 1, 2, 3 matter (each tour and its reverse cost the same here, since this matrix happens to be symmetric):

Answer 80.

Follow one state to see the machinery. f(0b1011, 3) means cities 0, 1 and 3 are visited and we stand in city 3. Only city 2 remains, so the cost is dist[3][2] + f(0b1111, 2) = 30 + dist[2][0] = 30 + 15 = 45. And f(0b0011, 1) — cities 0 and 1 visited, standing in city 1 — tries city 2 (35 + f(0b0111, 2)) and city 3 (25 + f(0b1011, 3) = 25 + 45 = 70), keeping the cheaper. That 45 is reused by every partial tour that arrives at the same situation, which is precisely the saving over brute force.

The signal for this technique is specific and easy to spot: the state needs to remember a set of things already used, and the number of things is small — roughly 20 or fewer. That size limit is not a coincidence; it is the constraint telling you the intended solution. If a problem caps n at 20 or so when the natural approach is factorial, a bitmask table is almost certainly what is wanted.

Common instances: assigning n jobs to n workers at minimum cost, counting the ways to pair people up, covering a board with dominoes column by column, choosing an ordering of tasks with prerequisites and switching costs, or partitioning items into groups that each satisfy some rule.

Two habits to take away.

A set can be an array index. Whenever "which ones have I already used?" belongs in your state and the universe is small, reach for an integer mask before reaching for a hash of sets — it makes the table a plain array and the transitions single instructions.

Read the constraints as a hint about the technique. N up to 20 with a factorial-looking problem means bitmask. N up to a few hundred with an interval-looking problem means an O(N³) interval table. N up to 100000 means something linear or logarithmic. The bounds are not decoration; they are the clearest signal the problem gives you about which of these tools you are expected to reach for.