Dynamic programming I

1 · When does DP apply? advanced

Start with the moment that made this click for a lot of people. You write the textbook recursive Fibonacci — three lines, elegant, obviously correct. It returns fib(10) instantly. Then someone types fib(50) and your program simply… hangs. Not crashes, not errors — just sits there, apparently forever. You didn't write a bug. You wrote something correct that quietly does billions of times more work than it needs to, because it keeps re-solving the exact same tiny problems over and over. Dynamic programming is the discipline that notices "wait, I've already answered this" and never answers it twice.

Here's the everyday analogy. Imagine a group project where five people are each asked to "compute the total budget." If nobody talks to anybody, all five independently re-add the same line items — five times the work for one answer. Now imagine one shared whiteboard: the first person to compute a subtotal writes it up, and everyone else just reads it. That whiteboard is memoization. DP is nothing more exotic than "do the work once, write the answer on a whiteboard, and look it up instead of redoing it." The whole subject is that idea, applied carefully.

But DP doesn't magically speed up every slow recursion — it only helps when the problem has the right shape, and knowing that shape is the real skill. The common mistake is reaching for a DP table on a problem where the subproblems never actually repeat (nothing to cache) or where stitching optimal small answers together does not give an optimal big answer — in which case the table is either useless or, worse, silently wrong. So before writing a single line of code, you check for two properties.

DP needs two properties. Overlapping subproblems: a naive recursion solves the same smaller problem many times. Optimal substructure: an optimal solution is built from optimal solutions to subproblems. If both hold, cache the subproblem answers and the exponential blowup collapses to polynomial. Miss either one and DP is the wrong tool: no overlap means caching buys you nothing (that's ordinary divide-and-conquer, like merge sort's two disjoint halves), and no optimal substructure means the cached pieces can't be trusted to compose into the right whole.

The clearest illustration is Fibonacci. Naive recursion recomputes fib(k) exponentially often — the call tree branches into two at every level, so it balloons to roughly O(2ⁿ) calls, almost all of them redundant. Memoizing makes each of the n subproblems solved exactly once, collapsing the whole tree to O(n). Watch the call counter in the lab below: the same answer, computed with a few dozen calls instead of a few million. That gap — millions versus dozens — is dynamic programming.

pythoncalls = {"naive": 0, "memo": 0}

def fib_naive(n):
    calls["naive"] += 1
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)      # recomputes the same n repeatedly

def fib_memo(n, cache={}):
    calls["memo"] += 1
    if n < 2:
        return n
    if n not in cache:
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print("fib(30) =", fib_naive(30), "in", calls["naive"], "naive calls")
print("fib(30) =", fib_memo(30), "in", calls["memo"], "memoized calls")

fib(30) = 832040 in 2692537 naive calls
fib(30) = 832040 in 59 memoized calls

2 · Memoization vs tabulation intermediate

Picture two people solving the same jigsaw puzzle. The first grabs whatever piece the picture on the box points them toward, working inward from wherever their eye lands, and only reaches for a new piece when they actually need it — messy path, but they never touch a piece they don't require. The second lays out every edge piece first, then fills row by row in strict order, never jumping ahead. Both finish the same puzzle. That is exactly the difference between the two ways to do DP: the first is memoization (top-down, on demand), the second is tabulation (bottom-up, in order). They compute the identical answer with the identical big-O cost — the choice between them is about ergonomics and edge cases, not correctness.

Why does this deserve its own section instead of "just pick one"? Because each style has a failure mode the other doesn't, and interviewers love probing whether you know which. Here is the plain-language version of the trade. Memoization lets you keep the recursion you already wrote — you literally add a cache and a "have I seen this?" check, so it's the fastest way to get from a correct-but-slow recursion to a fast one. Its danger: it rides Python's call stack, and a deep chain of subproblems (think n = 100{,}000) can blow the recursion-depth limit and crash. Tabulation has no recursion and no stack risk, and it's usually a hair faster because it skips call overhead — but you must figure out the exact order to fill the table so every cell's dependencies already exist, and it eagerly computes every state even ones the answer never needs.

The mistake to name up front: beginners often think tabulation is "the real DP" and memoization is a lazy shortcut. Not so — they are two implementations of the same recurrence. If you can write the recurrence (state + transition), you can write it either way, and the smart move is to reach for whichever fits the problem: memoization when the recursion is natural and the state space is sparse (many states never get visited), tabulation when the recursion is deep or you want to later shrink the table to save memory. The diagram below shows the single pipeline both share: define the recurrence once, then realize it top-down or bottom-up.

There are two ways to fill the cache. Memoization (top-down) keeps the natural recursion and stores each answer the first time it is computed. Tabulation (bottom-up) throws away recursion and fills an array in dependency order. Same complexity; different trade-offs.

3 · Climbing stairs — the smallest real DP intermediate

Here's a question that looks like it needs clever combinatorics but doesn't. You're standing at the bottom of a staircase with n steps. Each stride you take moves you up either 1 step or 2. How many distinct ways can you reach the top? Most people freeze and start trying to enumerate paths by hand — 1+1+1, 1+2, 2+1 — and immediately lose track for anything past n=4. The trick is to stop thinking about the whole journey and ask one small question instead: how did I arrive at the very last step?

There are only two possible final moves. Either your last stride was a single step (so just before it you were standing on step n-1), or it was a double step (so you were on step n-2). Those are the only two ways to land on step n, and they don't overlap. So the number of ways to reach the top is simply the number of ways to reach n-1 plus the number of ways to reach n-2. That single sentence is the whole recurrence — and notice we never had to enumerate a single full path. This is the payoff of DP thinking: reduce a big count to a sum of two smaller counts you'll compute the same way.

The analogy that sticks: it's like counting the ways water can flow into a bucket that has exactly two feeder pipes. The total inflow is just the sum of what comes through each pipe — and each pipe's flow is itself the sum of its two feeders, all the way back to the source. The common trap here is botching the base cases: people set dp[0]=0 thinking "zero steps means no ways," but there's exactly one way to "already be" at the bottom (do nothing), so dp[0]=1. Get the base wrong and every count above it is off. Now apply the five-line method and watch the code fall out mechanically.

You climb n stairs taking 1 or 2 steps at a time; how many distinct ways? Apply the method. State: dp[i] = ways to reach step i. Transition: you arrive at i from i-1 (a 1-step) or i-2 (a 2-step), so dp[i]=dp[i-1]+dp[i-2]. Base: dp[0]=dp[1]=1. It is Fibonacci in disguise — Θ(n) time, and Θ(1) space once you keep only two values. That last point is worth savoring: because dp[i] only ever looks back at the two cells immediately behind it, you never need the whole array — two rolling variables suffice, and an O(n)-space table shrinks to O(1). That "how far back does the recurrence reach?" question is how you space-optimize almost any 1-D DP.

pythondef climb_table(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1                       # base cases
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]       # transition
    return dp[n]

def climb_o1(n):
    a, b = 1, 1                             # only the last two states matter
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print([climb_table(n) for n in range(1, 9)])
print("space-O(1) agrees:", all(climb_table(n) == climb_o1(n) for n in range(1, 30)))

[1, 2, 3, 5, 8, 13, 21, 34]
space-O(1) agrees: True

4 · House robber — a real choice per state advanced

Climbing stairs was really just counting — this is the first problem where you have to decide. Picture a street of houses, each with a known amount of cash inside, and a rule enforced by a silent alarm: rob two adjacent houses and you're caught. Your job is to walk the street and choose a subset of non-adjacent houses that maximizes the total loot. The naive instinct — "just grab every house with a big number" — falls apart the moment two fat targets sit side by side, because you can only take one. And the greedy "always take the richer of two neighbors" heuristic quietly fails too: sometimes skipping a good house unlocks two even better ones further down.

The everyday version of this is the calendar you've all fought with. You're offered a stream of one-hour gigs, some paying more than others, and you can't take two that touch. Do you accept the $200 slot at 2pm, or skip it so you're free for the $150 at 2pm and the $180 at 3pm? You can't answer greedily — you have to weigh "take this and jump past its neighbor" against "skip this and keep my options open." That is precisely the house-robber decision, and it's the shape underneath a huge fraction of real DP problems.

Here's the key mental move: instead of agonizing over the whole street at once, stand at house i and ask one crisp question — what's the best I can do considering only houses 0 through i? Two futures branch from here. If I skip house i, my best is whatever I'd already achieved through house i-1. If I rob house i, I collect its cash plus the best I could do through house i-2 (because i-1 is now off-limits). I take the larger of those two. The single most common bug is writing the "rob it" branch alone and forgetting the "skip it" alternative — the max is not decoration, it's the entire point: it's where the choice lives, letting the DP quietly reject a tempting house when passing it up pays more.

Houses in a row hold cash; you cannot rob two adjacent houses. Maximize the loot. This introduces a genuine decision at each state. State: dp[i] = max loot considering houses 0..i. Transition: either skip house i (dp[i-1]) or rob it and add nums[i]+dp[i-2]; take the max. That 'skip vs take, keep the better' shape is the heart of most DP.

pythondef rob(nums):
    if not nums:
        return 0, []
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1, n):
        take = nums[i] + (dp[i - 2] if i >= 2 else 0)
        skip = dp[i - 1]
        dp[i] = max(take, skip)
    # reconstruct which houses were robbed
    chosen, i = [], n - 1
    while i >= 0:
        take = nums[i] + (dp[i - 2] if i >= 2 else 0)
        if take >= dp[i - 1] if i >= 1 else True:
            if (dp[i] == take):
                chosen.append(i); i -= 2
                continue
        i -= 1
    return dp[-1], sorted(chosen)

loot, houses = rob([2, 7, 9, 3, 1])
print("max loot:", loot, "robbing house indices:", houses)
print("check no two adjacent:", all(houses[k+1]-houses[k] >= 2 for k in range(len(houses)-1)))

max loot: 12 robbing house indices: [0, 2, 4]
check no two adjacent: True

5 · Coin change — minimization & unbounded choices advanced

This is the problem that has quietly shipped bugs into real payment and loyalty systems. A cashier making change reaches for the biggest coin that fits, then the next biggest, and so on — and for real-world currency that habit happens to be optimal, so it feels like a law of nature. It isn't. It's an accident of how national coin systems are designed. Swap in an arbitrary denomination set — a custom loyalty-point scheme, an in-game currency, a foreign mint from an old puzzle — and "grab the biggest" can hand you more coins than necessary, or even fail to make an amount it could have made. Teams learn this the hard way: the greedy change-maker passes every test written with US quarters and dimes, then miscounts in production the day someone configures a weird denomination.

Feel the trap concretely with coins {1, 3, 4} and a target of 6. Greedy grabs the 4 first (biggest that fits), leaving 2, which it must pay with 1+1 — three coins total. But the human eye sees it instantly: 3+3 is two coins. Greedy lost because committing to that 4 foreclosed the better pairing, and greedy never looks back. The lesson generalizes: the common mistake is trusting a locally-best choice to add up to a globally-best answer. Sometimes it does; often it doesn't; and "often" is where outages live.

DP fixes this by refusing to commit. Instead of picking one coin and hoping, it asks, for every amount from 1 up to the target: "what is the cheapest way to make this amount?" — and to answer for amount x it tries every coin as the last coin used, then keeps the best. The analogy is filling in a price chart from the smallest amount upward: by the time you reach amount x, you've already got the optimal answer for every smaller amount written down, so "make x using coin c" costs just one coin on top of the already-known best for x−c. Two subtleties worth flagging so they don't bite you: an unreachable amount must stay at infinity (not zero, or you'll fake a free solution), and dp[0]=0 because making zero costs no coins — the anchor the whole chart is built on.

Given coin denominations and an amount, find the fewest coins that sum to it (each coin usable unlimited times). State: dp[x] = min coins to make amount x. Transition: dp[x]=1+min(dp[x-c]) over coins c≤x. Base: dp[0]=0; unreachable amounts stay ∞. Complexity Θ(amount × #coins). This is where greedy fails — with coins {1,3,4} and amount 6, greedy takes 4+1+1=3 coins but the optimum is 3+3=2.

pythondef coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return dp[amount] if dp[amount] != INF else -1

def greedy(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c; count += 1
    return count if amount == 0 else -1

coins = [1, 3, 4]
print("DP optimum for 6:", coin_change(coins, 6))
print("greedy for 6:    ", greedy(coins, 6))
print("DP for 11 with [1,2,5]:", coin_change([1, 2, 5], 11))

DP optimum for 6: 2
greedy for 6:     3
DP for 11 with [1,2,5]: 3

6 · Longest increasing subsequence — two DP shapes expert

This one carries a lesson bigger than the problem itself: the same question can have two completely different DP "shapes," and reframing the state is how you drop a whole complexity class. First, the problem. A subsequence is what you get by deleting some elements from a list without reordering the rest — so from [3,1,4,1,5] the values [3,4,5] are a subsequence but [4,3] is not. The longest increasing subsequence (LIS) is the longest such run whose values strictly climb. Careful — this is not the longest increasing contiguous block; the winning elements can be scattered across the array as long as their order is preserved. Confusing "subsequence" with "substring" is the single most common misread, and it changes the answer entirely.

The intuitive DP mirrors house robber: stand at index i and ask "what's the longest increasing subsequence that ends right here at nums[i]?" To answer, look back at every earlier index j whose value is smaller — any of those could be the element just before i — and take the best chain you could extend. That gives a clean, correct answer, but notice the cost: for each of n positions you scan all the earlier ones, so it's O(n²). For a few thousand elements that's fine; for a stream of a million it's a wall.

Now the reframe that feels like magic the first time you see it. Play the card game "patience": deal cards one at a time, and place each onto the leftmost pile whose top card is not smaller. It turns out the number of piles you end up with equals the length of the LIS. Translated to code, you maintain a small array tails where tails[k] is the smallest value that could end an increasing subsequence of length k+1; each new element either extends the array (a new pile) or overwrites the first slot it's not smaller than — and because tails stays sorted, you find that slot with binary search in O(log n). One pass of n elements, each doing a log n lookup, is O(n log n). Same problem, same answer, a fundamentally cheaper state. One honest caveat so you don't over-claim in an interview: the tails array gives the correct length, but its contents are not themselves a valid LIS — reconstructing the actual subsequence needs extra bookkeeping.

The LIS of a sequence is the longest subsequence whose values strictly increase. The natural DP is Θ(n²): dp[i] = length of the best increasing subsequence ending at i, transitioning from any earlier j with nums[j]<nums[i]. A cleverer version uses binary search on a 'tails' array for Θ(n log n) — the patience-sorting insight.

pythonfrom bisect import bisect_left

def lis_n2(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)                    # dp[i]=LIS ending at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

def lis_nlogn(nums):
    tails = []                              # tails[k]=smallest tail of an LIS of length k+1
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

seq = [10, 9, 2, 5, 3, 7, 101, 18]
print("O(n^2) LIS:", lis_n2(seq), " O(n log n) LIS:", lis_nlogn(seq))
print("agree on random-ish input:",
      lis_n2([3,1,4,1,5,9,2,6,5,3,5]) == lis_nlogn([3,1,4,1,5,9,2,6,5,3,5]))

O(n^2) LIS: 4  O(n log n) LIS: 4
agree on random-ish input: True

Checkpoint expert

pythondef min_cost_climb(cost):
    n = len(cost)
    dp = [0] * n
    dp[0], dp[1] = cost[0], cost[1]
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
    return min(dp[-1], dp[-2])              # top is beyond the last stair

print(min_cost_climb([10, 15, 20]))            # 15
print(min_cost_climb([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6

15
6

pythondef count_change(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                         # coins OUTSIDE => combinations, not permutations
        for x in range(c, amount + 1):
            dp[x] += dp[x - c]
    return dp[amount]

print(count_change([1, 2, 5], 5))              # 4: 5, 2+2+1, 2+1+1+1, 1*5
print(count_change([2], 3))                    # 0
print(count_change([1, 5, 10, 25], 100))       # 242

4
0
242

pythondef word_break(s, words):
    wordset = set(words)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                            # empty prefix is segmentable
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordset:
                dp[i] = True
                break
    return dp[n]

print(word_break("leetcode", ["leet", "code"]))          # True
print(word_break("applepenapple", ["apple", "pen"]))     # True
print(word_break("catsandog", ["cats","dog","sand","and","cat"]))  # False

True
True
False

pythondef num_decodings(s):
    if not s or s[0] == "0":
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        if s[i - 1] != "0":                 # single digit 1-9
            dp[i] += dp[i - 1]
        if "10" <= s[i - 2:i] <= "26":      # pair 10-26
            dp[i] += dp[i - 2]
    return dp[n]

print(num_decodings("12"))     # 2  -> "AB","L"
print(num_decodings("226"))    # 3  -> "BZ","VF","BBF"
print(num_decodings("06"))     # 0  -> leading zero

2
3
0

pythondef max_product(nums):
    best = hi = lo = nums[0]
    for x in nums[1:]:
        if x < 0:
            hi, lo = lo, hi                 # sign flip swaps roles
        hi = max(x, hi * x)
        lo = min(x, lo * x)
        best = max(best, hi)
    return best

def brute(nums):
    b = nums[0]
    for i in range(len(nums)):
        prod = 1
        for j in range(i, len(nums)):
            prod *= nums[j]; b = max(b, prod)
    return b

for t in ([2,3,-2,4], [-2,0,-1], [-2,3,-4], [2,-5,-2,-4,3]):
    print(t, "->", max_product(t), "brute:", brute(t))

[2, 3, -2, 4] -> 6 brute: 6
[-2, 0, -1] -> 0 brute: 0
[-2, 3, -4] -> 24 brute: 24
[2, -5, -2, -4, 3] -> 24 brute: 24

pythondef max_profit_cooldown(prices):
    if not prices:
        return 0
    hold = float("-inf")   # best profit while holding a share
    sold = 0               # best profit having just sold today
    rest = 0               # best profit resting (not holding, free to buy)
    for price in prices:
        prev_sold = sold
        sold = hold + price            # sell today
        hold = max(hold, rest - price) # keep holding, or buy from a rest day
        rest = max(rest, prev_sold)    # rest; can absorb yesterday's sale (cooldown)
    return max(sold, rest)

print(max_profit_cooldown([1, 2, 3, 0, 2]))   # 3: buy1 sell3, cooldown, buy0 sell2
print(max_profit_cooldown([1]))               # 0
print(max_profit_cooldown([6, 1, 3, 2, 4, 7]))# 6

3
0
6