Dynamic Programming Mastery

Try every choice, but answer each question only once

Write 12 as a sum of as few perfect squares as possible. The obvious plan is greedy: take the biggest square that fits, then repeat. That gives 9 + 1 + 1 + 1, four squares. But 4 + 4 + 4 needs only three. Grabbing the 9 looked best and still lost.

So try every choice instead. For each square that could come first, solve what is left and keep the best result. That is always correct, and as plain recursion it is hopeless: it makes 104 calls for n = 12, about 60 million for n = 50, and about 2.3 × 10¹⁵ for n = 100.

Yet for n = 100 the recursion can only ever ask 101 different questions: "what is the fewest squares that sum to m?" for m = 0 … 100. It asks the same ones over and over. Answer each one once, write the answer down, and n = 100 takes 625 small steps.

That is dynamic programming (DP) in two sentences. Try every choice, so you are right. Answer each distinct subproblem once, so you are fast. The rest of this lesson is technique for making both halves work on problems that don't hand you their subproblems.

Before you start. You should be comfortable with recursion: base cases, the call stack, and trusting the recursive call (Advanced Recursion & Backtracking). Memo tables here are dictionaries, sometimes keyed by tuples (Hash Maps & Sets). And the notebook model from Foundation: Arrays & Strings comes back in its most general form: before each step, ask what the next step needs to know about the past, and store only that.

🧠 About the name. Richard Bellman coined it in the 1950s. "Programming" meant planning, as in "linear programming", not writing code. By his own later account, he wanted a word for multistage, time-varying decision making that nobody in Washington could object to, and "dynamic" did both jobs. The "multistage decisions" part is the one to remember: a DP makes one decision per stage.

Hear the echo: what makes a problem DP

Smell: a recursive search that tries every choice, and whose calls repeat.

Here is the try-every-choice recursion for LeetCode 279: Perfect Squares. The contract: given n ≥ 1, return the fewest perfect squares (1, 4, 9, …) that sum to n.

import math

def num_squares_brute(n):
    if n == 0:
        return 0                            # the empty sum uses zero squares
    best = math.inf
    for k in range(1, math.isqrt(n) + 1):   # every square k*k <= n may go first
        best = min(best, 1 + num_squares_brute(n - k * k))
    return best

math.isqrt(n) is the integer square root, so the loop tries exactly the squares that fit. The function is correct because every decomposition of n starts with some square, and the loop tries all of them.

Predict first: while computing num_squares_brute(12), how many times is the subproblem for 11 solved? And the subproblem for 0?

That repetition has a name: overlapping subproblems. Different choice sequences (1 then 4, or 4 then 1) lead to the same smaller problem, and plain recursion solves it again each time. The number of calls grows exponentially while the number of distinct questions grows by one:

Not every recursion overlaps. Merge sort splits an array into two halves that share no elements. Every call works on a different slice, so a cache would never get a hit. That is plain divide and conquer. DP pays off only when the same subproblem is reached along different paths.

The cut-and-paste test

Remembering one number per subproblem is only safe if the best answer for 12 can be built from the best answers for smaller amounts. Here it can. Suppose a best decomposition of 12 starts with 4. The remaining squares sum to 8. If they were not a best decomposition of 8, you could cut them out, paste in a shorter one, and get a decomposition of 12 that beats the best. That is impossible. So:

best(12) = 1 + min( best(12 − 1), best(12 − 4), best(12 − 9) )

This is optimal substructure: an optimal solution is made of optimal solutions to its subproblems. It is what lets you replace "every way to decompose 8" with the single number best(8).

It can fail. Take the longest simple path (no city visited twice) between two cities. If the longest simple path from A to C passes through B, its A-to-B part need not be the longest simple path from A to B, because that longer A-to-B path might use cities the B-to-C part needs. The halves interfere, so the best halves don't combine into the best whole, and no small table solves it.

Counting problems need a different guarantee, because there is no optimum to cut and paste. "How many ordered ways can n be written as a sum of squares?" works because splitting by the first square gives cases that are disjoint (no way is counted in two branches) and exhaustive (every way lands in some branch). So the counts simply add. Feasibility problems ("can n be written as …?") combine their cases with or.

From recursion to a table

The recursion is right; it just forgets. There are two standard ways to make it remember.

Top-down: a notebook next to the recursion

Keep the recursion exactly as it is and add a dictionary, the memo, from subproblem to answer. Look there before doing any work, and write there before returning. This is memoization.

import math

def num_squares_memo(n):
    memo = {0: 0}                        # base case pre-filled; a fresh memo per call

    def solve(m):
        if m in memo:
            return memo[m]
        best = math.inf
        for k in range(1, math.isqrt(m) + 1):
            best = min(best, 1 + solve(m - k * k))
        memo[m] = best                   # store before returning
        return best

    return solve(n)

Now each m is worked out once. Every later request for it is a dictionary lookup.

Cost = states × work per state. There are n + 1 states, and state m tries ⌊√m⌋ squares, so the time is O(n√n): 661,750 inner steps for n = 10⁴, where the brute force would never finish. Extra space is O(n) for the memo, plus the recursion stack. solve(n) calls solve(n − 1), which calls solve(n − 2), and so on, so the stack grows n frames deep. In Python that depth is a real problem.

⚠️ Python's recursion limit. CPython allows about 1,000 nested calls by default (sys.getrecursionlimit()), then raises RecursionError. num_squares_memo(1000) already fails, and LeetCode 279 allows n up to 10⁴. sys.setrecursionlimit(20000) gets this dictionary version through n = 10⁴ on CPython 3.14, but it is a patch: in the same test, the functools.cache version below overflowed the interpreter's C stack near depth 8,000 even with the higher limit. When the depth can reach thousands, go bottom-up. Java and C++ have no call-count limit, but a deep enough recursion still overflows the thread's stack there too.

functools.cache does the memo bookkeeping for you:

import math
from functools import cache

def num_squares_cached(n):
    @cache                               # defined inside: each call gets a fresh cache
    def solve(m):
        if m == 0:
            return 0
        best = math.inf
        for k in range(1, math.isqrt(m) + 1):
            best = min(best, 1 + solve(m - k * k))
        return best

    return solve(n)

Two traps come with any memo:

⚠️ The key must capture everything the answer depends on. The memos above live inside the outer function, so every call starts fresh. The classic def f(amount, memo={}) default argument (or a module-level @cache) survives between calls instead. For Perfect Squares that would be harmless, because best(8) is 2 no matter who asks. It becomes a silent bug as soon as the answer depends on something that is not in the key:

import math

def min_coins(coins, amount, memo={}):       # BUG: one memo shared by every call
    if amount == 0:
        return 0
    if amount in memo:
        return memo[amount]
    best = math.inf
    for c in coins:
        if c <= amount:
            best = min(best, 1 + min_coins(coins, amount - c, memo))
    memo[amount] = best
    return best

print(min_coins([1, 5], 10))    # 2, correct
print(min_coins([1, 3], 9))     # 5: the cached answer for coins [1, 5]; the truth is 3

The fix is a fresh memo for every top-level call, or a key that includes everything the answer depends on, such as (tuple(coins), amount).

⚠️ "Not computed yet" must not look like an answer. If you preallocate memo = [0] * (n + 1) and treat 0 as "unknown", then state 0, whose real answer is 0, looks uncomputed forever. Mark unknown cells with None (or −1 when real answers are never negative), or use a dictionary and in.

Bottom-up: fill the notebook in order

Top-down lets the recursion discover the order. Bottom-up chooses the order in advance: fill a table from the smallest subproblem up, so every value a cell needs is already there. This is tabulation.

import math

def num_squares(n):
    dp = [0] + [math.inf] * n          # dp[m] = fewest squares summing to m; n + 1 slots
    for m in range(1, n + 1):
        for k in range(1, math.isqrt(m) + 1):
            dp[m] = min(dp[m], dp[m - k * k] + 1)
    return dp[n]

This trace for n = 12 was printed by the loop. Each "try" shows a square and the candidate dp[m − square] + 1 it produces:

The last row replays the hook: the 9 leads to dp[3] + 1 = 4, while the 4 leads to dp[8] + 1 = 3.

Why it works. The invariant: when the loop reaches m, the entries dp[0] … dp[m − 1] are final. Every square is at least 1, so m − k² < m, and each cell reads only cells the loop has already finished. By induction, dp[m] is final when the loop leaves it.

The cost is O(n√n) time and O(n) extra space, with no recursion at all. The table has n + 1 slots because the base case lives at index 0 and the answer at index n.

⚠️ Start a min table at infinity, not 0. With dp = [0] * (n + 1), every min(dp[m], …) keeps the 0 that is already there, and the function returns 0 for every n. The starting value must be the identity of the combine step: inf for min, -inf for max, 0 for adding up counts, False for "or". The base case is a separate decision: dp[0] = 0 because the empty sum uses zero squares.

"Sparse" matters more than it sounds. If a problem's subproblems are n // 2 and n // 3, then from n = 2 × 10⁹ the recursion only ever reaches numbers of the form n // (2ᵃ·3ᵇ). That is 259 distinct values, while a table indexed 0 … n would need two billion cells. Neither style is faster by rule. In Python, function calls and dictionary lookups cost more than list indexing, so a table usually wins by a constant factor (about 1.9× for Perfect Squares at n = 10⁴) unless top-down gets to skip most of the states.

Test the fast version against the slow one. The brute force is too slow for real inputs, but it makes a perfect reference on small ones:

import random

def check(fast, slow, trials=300, max_n=25):
    for _ in range(trials):
        n = random.randint(0, max_n)
        assert fast(n) == slow(n), n
    print("all matched")

check(num_squares, num_squares_brute)
check(num_squares_memo, num_squares_brute)

Your turn: count instead of minimize. Write count_sums(n), the number of ordered ways to write n as a sum of perfect squares, so 1 + 4 and 4 + 1 count separately. Keep the same state and the same choices. What changes? What is count_sums(0)? Predict count_sums(5) and count_sums(12).

import math

def count_sums(n):
    ways = [1] + [0] * n                 # ways[0] = 1: the empty sum
    for m in range(1, n + 1):
        for k in range(1, math.isqrt(m) + 1):
            ways[m] += ways[m - k * k]   # split by the first square
    return ways[n]

Design the state

Smell: your recurrence needs a fact about the past that the subproblem doesn't record.

Perfect Squares handed you its state: the amount left. Most problems don't, and designing the state is the real skill. A short recipe keeps it honest:

1. State in one sentence, with units. "dp[m] = the fewest squares that sum to exactly m." If you can't say it, you can't write the recurrence.
2. Recurrence from one decision. Look at the first (or last) choice, list the options, and combine them with min, max, + or or.
3. Base cases for states that need no decision, and starting values for the rest: the identity of the combine step. For max and min problems, −inf and inf also mark states that are impossible.
4. Order: which states must be ready first (next section).
5. Where the answer lives: one cell such as dp[n], or a combination such as max(dp).
6. Cost: states × work per state, plus the stack for top-down.

Step 5 hides a real design choice. "Best among the first i elements" puts the answer in the last cell. "Best for a solution that ends exactly at i" puts it in max(dp), but it makes the recurrence easier, because you know the last element. Kadane's algorithm (Maximum Subarray Sum) and longest increasing subsequence (1D DP Problems) both use "ends at i".

The stock that needs a nap

In the foundation lesson you solved Best Time to Buy and Sell Stock with a two-number notebook: the cheapest earlier price and the best profit so far. Now change the rules. In LeetCode 309: Best Time to Buy and Sell Stock with Cooldown you may trade as often as you like while holding at most one share, but after a sale you must skip a day before buying again. Prices [1, 2, 3, 0, 2] give 3: buy at 1, sell at 2, wait a day, buy at 0, sell at 2.

Predict first: is "best profit up to day i" enough state?

The three modes, and the moves between them from one day to the next:

   rest again       keep holding
     ┌───┐             ┌───┐
     ▼   │     buy     ▼   │     sell
     REST ───────────▶ HOLD ───────────▶ SOLD
      ▲                                    │
      └──────────── cooldown day ──────────┘

HOLD means you own a share. SOLD means you sold today. REST means you own nothing and did not sell today, so you may buy tomorrow. Each mode gets one number: the best profit so far over all legal histories that end today in that mode.

import math

def max_profit_cooldown(prices):
    if not prices:
        return 0
    hold = -prices[0]            # bought on day 0
    sold = -math.inf             # "sold on day 0" is impossible
    rest = 0                     # did nothing
    for price in prices[1:]:
        hold, sold, rest = (
            max(hold, rest - price),    # keep holding, or buy today
            hold + price,               # sell the share held yesterday
            max(rest, sold),            # rest again, or sit out the cooldown day
        )
    return max(sold, rest)       # never finish holding a share

End-of-day values on [1, 2, 3, 0, 2], printed by the loop:

The answer is max(3, 2) = 3. Watch day 3: hold jumps to 1 because rest was 1 (the day-1 sale sat out its cooldown on day 2), and 1 − 0 = 1.

Why it works. Every legal trading history is a walk through the diagram, one arrow per day. Each variable holds the best profit among the walks that end in its mode today, and each update considers every arrow into that mode. The diagram enforces the cooldown by itself: the only way into HOLD is from HOLD or REST, and SOLD reaches REST only after one day. The cost is O(n) time for n prices and O(1) extra space.

Two traps:

• Update all three from yesterday's values. The tuple assignment evaluates every right-hand side before it assigns anything. Write the updates as three separate lines and sold reads today's hold, while rest reads today's sold. The cooldown silently disappears, and [1, 2, 3, 0, 2] returns 4.
• Impossible states start at −inf, not 0. Nobody can have sold on day 0. Here sold = 0 happens to be harmless, because a fake zero-profit sale is never better than rest, which is also 0. In other state machines a fake 0 is a free lunch. In the two-transaction version of this problem, for example, starting "holding the second share" at 0 lets the code sell a share it never paid for.

Every dimension multiplies the work. Allow at most k transactions and the mode must also count how many you have used: about 2k modes and O(nk) time. Before adding a dimension, check whether two candidate states always allow the same moves. If they do, merge them. Here "rested yesterday" and "sold yesterday, so today is the cooldown day" both end today with no share and no sale today. They allow the same moves tomorrow, so both are just REST.

Your turn. Remove the cooldown and charge a fee of fee per sale instead (LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee). Which modes do you still need? Write it with O(1) extra space, and trace prices = [1, 3, 2, 8, 4, 9] with fee = 2.

def max_profit_fee(prices, fee):
    hold, free = -prices[0], 0
    for price in prices[1:]:
        hold, free = max(hold, free - price), max(free, hold + price - fee)
    return free

Fill order: a cell only after its inputs

Smell: the bottom-up version returns wrong numbers, often too small because it read cells that were still 0, while the memoized version is right.

Top-down gets its order for free, because a call simply waits for the calls it makes. Bottom-up needs a loop order in which every cell's inputs are filled before the cell. Draw the arrows first, then write the loops.

Longest Palindromic Subsequence

LeetCode 516: Longest Palindromic Subsequence asks for the length of the longest subsequence of s that reads the same in both directions. For "bbbab" it is 4 ("bbbb"). It is a subsequence, so characters may be skipped. The longest palindromic substring, which must be contiguous, is a different problem with a different fast method; see String Algorithms.

The state is dp[i][j], the longest palindromic subsequence inside s[i..j] (both ends inclusive). The decision is about the two end characters:

• If s[i] == s[j], use them as the outer pair: dp[i][j] = dp[i + 1][j − 1] + 2. This never loses. If a best palindrome uses s[i] but not s[j], swap its last character (a copy of s[i]) for s[j]; if it uses neither end, adding both makes it longer. Either way some best palindrome uses both ends.
• Otherwise at least one end is not used: dp[i][j] = max(dp[i + 1][j], dp[i][j − 1]).
• Base cases: dp[i][i] = 1, and an empty range (i > j) is 0.

Here is what cell X = dp[i][j] reads:

            col j-1   col j
  row i    [  L  ]   [  X  ]     L = dp[i][j-1]     same row, one left
  row i+1  [  D  ]   [  B  ]     D = dp[i+1][j-1]   row below, one left
                                 B = dp[i+1][j]     row below

Every input is in the row below or to the left. So row i + 1 must be finished before row i: rows go bottom to top. Within a row the left cell comes first: columns go left to right.

def longest_pal_subseq(s):
    n = len(s)
    if n == 0:
        return 0
    dp = [[0] * n for _ in range(n)]      # cells with i > j stay 0: empty ranges
    for i in range(n - 1, -1, -1):        # rows bottom to top
        dp[i][i] = 1
        for j in range(i + 1, n):         # columns left to right
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

When j = i + 1 and the two characters match, dp[i + 1][j − 1] is dp[i + 1][i], a cell below the diagonal that stays 0. That 0 is the empty middle of a two-letter palindrome.

The finished table for "bbbab", printed from the code (· marks unused cells):

Predict first: a learner writes the outer loop as for i in range(n):, top to bottom, and changes nothing else. What does "bbbab" return?

The general rule. Subproblems and their "reads from" arrows form a graph. A bottom-up order exists exactly when that graph has no cycle, and any order that puts every cell after its inputs works. For LPS, filling by range length (every length-2 range, then every length-3 range, and so on) is another valid order, because every input is a shorter range. When a bottom-up version misbehaves, print its table on a tiny input: cells read before they were filled show up as stray zeros.

⚠️ If the arrows form a cycle, it isn't DP. Suppose you may step left or right along a line and want the fewest steps to a target. "Fewest steps from 5" depends on "fewest steps from 6", which depends on "fewest steps from 5". There is no order to fill, and memoized recursion goes around the cycle until the recursion limit stops it. That is a shortest-path problem, solved with BFS and a visited set (Shortest Path Algorithms).

LPS fills about n²/2 cells with O(1) work each, so it takes O(n²) time and O(n²) space for a string of length n. Later sections shrink that space and recover the palindrome itself.

Boss level: Burst Balloons, or choose the last move

In LeetCode 312: Burst Balloons, balloons carry the values nums. Bursting a balloon earns left × value × right, where left and right are its current neighbours; a missing neighbour counts as 1. Burst them all and maximize the total. [3, 1, 5, 8] gives 167.

Try the natural decision first: which balloon bursts first? After it pops, its two neighbours become adjacent, so the left part's scores depend on what is still on the right. The subproblems are not independent, and the state falls apart.

Now flip it: which balloon in a range bursts last? Put walls at positions left and right, and let k be the last balloon burst between them. Until that moment k stands between the two sides, so balloons on the left only ever neighbour balloons in left … k, and the right side only k … right. The two sides are independent subproblems. When k finally bursts, its neighbours are exactly the walls, so it earns vals[left] × vals[k] × vals[right].

def max_coins(nums):
    vals = [1] + nums + [1]                 # walls worth 1 at both ends
    n = len(vals)
    dp = [[0] * n for _ in range(n)]        # dp[l][r]: best for balloons strictly between l and r
    for gap in range(2, n):                 # shorter ranges first
        for left in range(n - gap):
            right = left + gap
            for k in range(left + 1, right):   # k = the last balloon burst between the walls
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + vals[left] * vals[k] * vals[right] + dp[k][right],
                )
    return dp[0][n - 1]

print(max_coins([3, 1, 5, 8]))   # 167

The order: dp[left][right] reads dp[left][k] and dp[k][right], and both have a smaller gap, so filling gap by gap works. A gap of 1 has no balloon inside and stays 0. The cost for n balloons is O(n²) ranges × O(n) choices of k, so O(n³) time and O(n²) space.

The best order for [3, 1, 5, 8] bursts 1, 5, 3, 8: 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 15 + 120 + 24 + 8 = 167. A plausible greedy rule, "burst the smallest balloon first", scores only 78.

💡 When choosing "first" tangles the state, try choosing "last". The last action often splits the problem into parts that were independent all along.

Your turn. A recurrence computes dp[i][j] from dp[i − 1][j] and dp[i][j + 1]. Which way should the row loop run, and which way the column loop?

for i in range(rows):
    for j in range(cols - 1, -1, -1):
        ...

Walk it back: recovering the choices

Smell: the problem wants the actual solution (the squares, the palindrome, the trades), not just its size.

A DP table stores the best value of every subproblem, and that is enough to recover the choices. At each state, some option produced the stored value. Follow that option to the next state and repeat until you reach a base case. There are two ways to know which option won:

1. Record the winning choice in a second table while you fill the first.
2. Re-derive it afterwards: at each state, check which option reproduces the stored value.

import math

def num_squares_with_parts(n):
    dp = [0] + [math.inf] * n
    choice = [0] * (n + 1)                    # choice[m] = the square that won at m
    for m in range(1, n + 1):
        for k in range(1, math.isqrt(m) + 1):
            if dp[m - k * k] + 1 < dp[m]:     # strict <: keep the first winner
                dp[m] = dp[m - k * k] + 1
                choice[m] = k * k
    parts = []
    m = n
    while m > 0:                              # follow the choices down to 0
        parts.append(choice[m])
        m -= choice[m]
    return dp[n], parts

num_squares_with_parts(12) returns (3, [4, 4, 4]). choice[12] is 4 (the winner in the trace table's last row), then choice[8] is 4, then choice[4] is 4. The walk adds only O(number of parts) to the fill. Ties go to the first square tried because of the strict <: at m = 10, the squares 1 and 9 both give 2, so num_squares_with_parts(10) returns (2, [1, 9]).

"DP gives you the value but not the decisions" is a myth; recovering one optimal solution is almost free. The genuine limit is listing all optimal solutions. There can be exponentially many, so that work is as large as its output, and a backtracking walk over the table is the tool.

Your turn. Rebuild the palindrome itself. Assume lps_table(s) is longest_pal_subseq with its last line changed to return dp. Start at (0, n − 1) and at each step let the table tell you which way the optimum went. What do you get for "character"?

def lps_string(s):
    if not s:
        return ""
    dp = lps_table(s)
    left, right = [], []
    i, j = 0, len(s) - 1
    while i <= j:
        if i == j:                             # one middle character
            left.append(s[i])
            break
        if s[i] == s[j]:                       # the ends form the outer pair
            left.append(s[i])
            right.append(s[j])
            i, j = i + 1, j - 1
        elif dp[i + 1][j] >= dp[i][j - 1]:     # the optimum drops s[i]
            i += 1
        else:                                  # the optimum drops s[j]
            j -= 1
    return "".join(left) + "".join(reversed(right))

Shrink the table

Smell: each row or cell reads only a fixed window of earlier ones, but you keep all of them.

Once no future cell will read a row, you can drop it. There are three levels of shrinking.

1. Rolling variables. Fibonacci (LeetCode 509: Fibonacci Number) reads only the previous two values. Plain recursion makes 331,160,281 calls to compute F(40), a table needs 41 cells, and two variables are enough:

def fib(n):
    a, b = 0, 1                  # F(0), F(1)
    for _ in range(n):
        a, b = b, a + b          # slide the window one step
    return a

That is O(n) time and O(1) extra space, and fib(10) is 55. The stock machine already did the same thing: three variables instead of three arrays.

2. Rolling rows. If row i of a 2D table reads only row i + 1 and its own row, keep just two rows. Here is LPS in O(n) space:

def lps_two_rows(s):
    n = len(s)
    below = [0] * n                    # row i + 1
    for i in range(n - 1, -1, -1):
        row = [0] * n                  # row i, freshly zeroed
        row[i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                row[j] = below[j - 1] + 2
            else:
                row[j] = max(below[j], row[j - 1])
        below = row
    return below[n - 1] if n else 0

The time is still O(n²), but only two rows are alive at any moment, so the extra space is O(n).

⚠️ If you recycle the two buffers instead of allocating a fresh row (below, row = row, below), the recycled row still holds values from two rows ago. Assign every cell before anything reads it, and never fold a new value into whatever a recycled cell holds (row[j] = min(row[j], …)) unless you reset that cell first.

3. One array, updated in place. When row i reads only row i − 1, you can sometimes overwrite a single array. Then the direction of the inner loop decides what you read: values from the previous row, or values already updated in this one.

Plot twist: the loop direction changes the problem

LeetCode 416: Partition Equal Subset Sum asks whether nums can be split into two groups with equal sums. That is the same as asking whether some subset reaches target = sum(nums) // 2. The 2D state is "using the first i numbers, can I make sum s?" Each number is either skipped (the row above, same s) or used once (the row above, s − x). In one array:

def can_make(nums, target):
    can = [True] + [False] * target      # can[s]: some subset of the numbers so far sums to s
    for x in nums:
        for s in range(target, x - 1, -1):   # DOWNWARD: can[s - x] is still last row's value
            if can[s - x]:
                can[s] = True
    return can[target]

def can_partition(nums):
    total = sum(nums)
    return total % 2 == 0 and can_make(nums, total // 2)

can_partition([1, 5, 11, 5]) is True (11 = 1 + 5 + 5), and can_partition([1, 2, 3, 5]) is False because the total, 11, is odd. For n numbers the cost is O(n · target) time and O(target) extra space.

Predict first: flip the inner loop to range(x, target + 1), upward. What does can_make([3], 6) return?

The 0/1 knapsack, where each item has a weight and a value, has the same shape, with max in place of or. 2D DP & Grid Problems works through it, along with rolling rows on grids.

What shrinking costs you. A rolled table can't be walked back directly, because the rows the walk needs are gone. (Advanced methods such as Hirschberg's algorithm recompute parts of the table to recover a solution in linear space, at extra cost.) It is also harder to print and debug. Get the full table right and tested first, then shrink it.

Your turn. Turn can_make into count_subsets(nums, target), the number of subsets that sum to target. What changes and what stays? Predict count_subsets([1, 2, 3, 3], 6).

def count_subsets(nums, target):
    ways = [1] + [0] * target            # one subset (the empty one) sums to 0
    for x in nums:
        for s in range(target, x - 1, -1):   # still downward: each number once
            ways[s] += ways[s - x]
    return ways[target]

DP or greedy?

Smell: each step offers several choices, and one of them looks obviously best.

A greedy algorithm takes the obvious choice and never looks back. DP keeps every choice open and lets the table decide. Greedy is faster and simpler, and it is correct when the greedy-choice property holds: some optimal solution starts with the greedy choice. Both approaches need optimal substructure; greedy additionally needs that one choice to be safe. Don't use a greedy rule until you can prove the property. One that passes the examples but has no proof is a guess.

You met one failure in the hook: 12 = 9 + 1 + 1 + 1 against 4 + 4 + 4. Coins behave the same way. With coins [1, 3, 4] and amount 6, largest-first takes 4 + 1 + 1, three coins, while 3 + 3 uses two. With US coins [1, 5, 10, 25], largest-first happens to be optimal; it matched the DP answer for every amount below 2,000. That is a property of that particular coin system, not of coins in general. The full Coin Change DP is in 1D DP Problems.

Predict first: coins [1, 7, 10], amount 14. How many coins does largest-first use, and how many does DP find?

Same meetings, two contracts

You have one room and a list of meetings, each with a start and an end time.

Attend as many meetings as possible. Greedy works. Sort by end time, then take every meeting that starts no earlier than the last one you took ends. The proof is an exchange argument. Take any optimal schedule and swap its first meeting for the meeting that ends earliest overall. The new first meeting ends no later, so everything after it still fits. The schedule is still optimal, and now it starts with the greedy choice; repeat the argument on the rest. The cost is O(n log n), for the sort. LeetCode 435: Non-overlapping Intervals asks the mirror question, the fewest meetings to remove, and the same greedy answers it.

Earn as much as possible. Now each meeting pays a different amount, as in LeetCode 1235: Maximum Profit in Job Scheduling. The exchange argument breaks, because the earliest-ending meeting that still fits may pay 40 while the meeting it blocks pays 70. Take the jobs (start, end, profit) = (1, 3, 50), (2, 4, 10), (3, 5, 40) and (3, 6, 70). Earliest-end greedy takes 50 and then 40, for 90. The best is 50 + 70 = 120.

So use DP. Sort the jobs by end time. The state is best[i], the most you can earn using only the first i jobs in that order. The decision is about job i: skip it (best[i − 1]), or take it and add the best you can earn from jobs that end by its start. Because the jobs are sorted by end, "jobs that end by time s" is a prefix of the list, and binary search finds its length.

import bisect

def job_scheduling(start, end, profit):
    jobs = sorted(zip(end, start, profit))          # by end time
    ends = [e for e, _, _ in jobs]
    best = [0] * (len(jobs) + 1)                    # best[i]: using only the first i jobs
    for i, (e, s, p) in enumerate(jobs, 1):
        j = bisect.bisect_right(ends, s, 0, i - 1)  # how many earlier jobs end by s
        best[i] = max(best[i - 1], best[j] + p)     # skip job i, or take it
    return best[-1]

print(job_scheduling([1, 2, 3, 3], [3, 4, 5, 6], [50, 10, 40, 70]))   # 120

A job may start at the exact time another ends, so bisect_right counts an end equal to s as compatible. For n jobs the cost is O(n log n) time (the sort plus n binary searches) and O(n) extra space. Sorting first is itself a state-design move: it turned "every set of compatible earlier jobs" into "a prefix", which one index can describe.

When the table is too big

"States × work" is fast only when the number of states is small. can_make takes O(n · target) time. That is polynomial in the value of target, not in the size of the input: a single 10-digit target means a table of about 10¹⁰ cells. Running time like this is called pseudo-polynomial. When the values are huge but there are few numbers, count the other way: 20 numbers have only 2²⁰, about a million, subsets.

DP also doesn't help when:

• nothing repeats, as in merge sort or binary search, so a cache never gets a hit;
• the task is to list every solution (all subsets, all orderings). The output itself is exponential, so use backtracking (Advanced Recursion & Backtracking);
• the subproblems depend on each other in a cycle, which calls for a graph search such as BFS instead.

Your turn. DP, greedy, or neither?

1. Attend as many non-overlapping talks as possible from a conference schedule.
2. Pay 12 with as few coins as possible from [1, 6, 10].
3. Print every way to pay 12 with coins from [1, 6, 10].

Final round: no label on the problem

Real problems don't say "DP". For each one below, decide whether it is DP and design the state, or whether something simpler is enough. Then write it.

Challenge 1: Minimum Cost For Tickets

LeetCode 983: Minimum Cost For Tickets. You travel on the days in days (strictly increasing, each between 1 and 365). A 1-day pass costs costs[0], a 7-day pass costs[1] and a 30-day pass costs[2]; a 7-day pass bought on day d covers days d to d + 6. Find the minimum total cost. With days = [1, 4, 6, 7, 8, 20] and costs = [2, 7, 15] the answer is 11.

Before peeking, answer these:

1. Does a rule such as "buy a 7-day pass whenever at least four trips fall in the next week" come with a proof?
2. What is the state? What does day d need to know about the past?
3. What happens on a day you don't travel?

def mincost_tickets(days, costs):
    travel = set(days)
    last = days[-1]
    dp = [0] * (last + 1)                    # dp[d]: cover every travel day <= d
    for d in range(1, last + 1):
        if d not in travel:
            dp[d] = dp[d - 1]                # nothing to cover today
            continue
        dp[d] = min(
            dp[d - 1] + costs[0],            # a 1-day pass for day d
            dp[max(0, d - 7)] + costs[1],    # a 7-day pass for days d-6 .. d
            dp[max(0, d - 30)] + costs[2],   # a 30-day pass for days d-29 .. d
        )
    return dp[last]

Challenge 2: Jump Game

LeetCode 55: Jump Game. You start at index 0, and nums[i] is the longest jump allowed from index i. Can you reach the last index? [2, 3, 1, 1, 4] → True, and [3, 2, 1, 0, 4] → False. There are up to 10⁴ numbers.

1. A table reach[i] ("can I get to index i?") works. What does it cost?
2. At any moment, what shape does the set of reachable indices have?
3. So how many numbers do you actually need to remember?

def can_jump(nums):
    reach = 0                            # every index <= reach is reachable
    for i, step in enumerate(nums):
        if i > reach:
            return False                 # stuck before index i
        reach = max(reach, i + step)
    return True

Challenge 3: Target Sum

LeetCode 494: Target Sum. Put + or − in front of every number in nums so that the total equals target, and count the ways. With nums = [1, 1, 1, 1, 1] and target = 3 there are 5 ways.

1. Brute force tries 2ⁿ sign patterns. What repeats?
2. Let P be the numbers that get +. What must sum(P) equal?
3. Which earlier function does that turn this into, and which loop direction does it need?
4. What if total + target is odd, or |target| > total?

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0                              # no subset can have that sum
    goal = (total + target) // 2
    ways = [1] + [0] * goal
    for x in nums:
        for s in range(goal, x - 1, -1):      # downward: each number once
            ways[s] += ways[s - x]
    return ways[goal]

Cheat sheet

Before moving on, pick one problem from this lesson, such as Perfect Squares, the cooldown stock or LPS, and rebuild it from a blank editor. Say the state in one sentence. Derive the recurrence from one decision. Name the base cases and starting values. Draw the arrows and pick the loop order. Then test it against the brute force on small random inputs. If you can also say which changed rule would break it (items reusable, a cooldown added, "first" instead of "last"), you are ready for the problem families.

Next: 1D DP Problems for the one-index family (Climbing Stairs, House Robber, Coin Change, Word Break, Decode Ways, Longest Increasing Subsequence), and 2D DP & Grid Problems for grids and two-string DP (Unique Paths, Longest Common Subsequence, Edit Distance, knapsack).