DP (Dynamic Programming)

The one-sentence version

Dynamic programming is recursion where the same subproblem comes back, so you answer each one once and look it up after that, and the whole skill is naming the state: the fewest numbers that fully describe “where am I in this problem”.

ELI5

How many ways can you climb a staircase taking one or two steps at a time?

You could try every route. Or notice: the ways to reach step 10 is ways to reach 9 plus ways to reach 8, because the last hop was a 1 or a 2. That’s the recurrence. Computed naively you’d work out “ways to reach 5” thousands of times, same question, same answer.

So you write the answer on the step. Next time you land there you read it. That sticky note is the memo. Filling the notes bottom-up instead of on demand is the table. Noticing you only ever read the two notes below you is the O(1) space trick.

ways(n) = ways(n-1) + ways(n-2)      # the recurrence
ways(1) = 1, ways(2) = 2             # the base cases

Every episode here is that idea with a different sticky note.

How to recognise it

Signal	Example
”count the number of ways”	Climbing Stairs (EP173), Unique Paths (EP183), Target Sum (EP179)
“minimum / maximum cost / profit / length”	House Robber (EP174), Buy Sell Stock (EP184), Cut a Stick (EP185)
“is it possible to…”	Subset Sum (EP178)
a choice at each step: take or skip	0/1 Knapsack (EP175, 177), House Robber (EP174)
the word subsequence (not subarray)	LIS (EP180–181), LCS (EP182)
two sequences compared position by position	LCS (EP182)
a grid you move right/down through	Unique Paths (EP183)
“optimal way to split / cut an interval”	Cut a Stick (EP185)
brute force is exponential; constraints are a few thousand	all fifteen

The anti-signals. “List all of them” means the output itself is exponential, that’s backtracking, Pattern 12, and no memo saves you. If a local choice is provably safe (always take the largest), it’s greedy; DP would be correct but wasteful. DP is for when the best-looking step now can ruin you later.

Contrast with Kadane. Kadane’s best_ending_here is a one-state DP. The difference is subarray (contiguous, Pattern 04) versus subsequence (skip freely, here). Once elements need not be adjacent the state must carry more than a running sum.

The method: four steps, every time

Shown once on House Robber; every episode reuses it.

1. Say the state in words. “f(i) = the most I can rob from houses 0..i.” Can’t finish the sentence, can’t write the code.

2. Write the recurrence as plain recursion. Exponential and correct.

def f(i):
    if i < 0: return 0
    return max(f(i - 1),              # skip house i
               f(i - 2) + nums[i])    # rob it, so i-1 is off limits

3. Add the memo. @lru_cache(None) on top. Now O(n), and nothing else changed.

4. Flip to a table, then shrink it. The table’s fill order is the reverse of the recursion’s call order: you fill what the recursion would have needed first.

dp = [0] * (n + 1)                    # dp[i+1] answers f(i); dp[0] is "no houses"
dp[1] = nums[0]
for i in range(1, n):
    dp[i + 1] = max(dp[i], dp[i - 1] + nums[i])

It only reads two cells back, so two variables do the job:

prev2, prev1 = 0, 0
for x in nums:
    prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1

EP176 does step 4 slowly, on purpose, the flip is where people lose the thread.

The shapes

Shape A: 1-D linear (looks back a fixed distance)

Fibonacci, Stairs, House Robber: dp[i] reads dp[i-1] and dp[i-2], so rolling variables always work. Buy Sell Stock (EP184) is the degenerate case: state is min_price_so_far, recurrence is best = max(best, price - min_so_far). Seeing it as DP gives the cooldown / k-transaction variants somewhere to attach.

Shape B: 0/1 knapsack (an item, a capacity, take or skip)

# dp[i][c] = best value using items[:i] with capacity c
for i in range(1, n + 1):
    w, v = weight[i - 1], value[i - 1]
    for c in range(W + 1):
        dp[i][c] = dp[i - 1][c]                                  # skip
        if c >= w:
            dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)       # take

Row i only reads row i - 1, so one row suffices, but the inner loop must run backwards:

dp = [0] * (W + 1)
for w, v in zip(weight, value):
    for c in range(W, w - 1, -1):          # <- BACKWARDS
        dp[c] = max(dp[c], dp[c - w] + v)

Forwards, dp[c - w] already contains this item and you take it twice, that’s the unbounded knapsack, a different problem. Say this out loud; it’s the follow-up question.

Subset Sum (EP178) is knapsack with a boolean: dp[c] |= dp[c - x]. Target Sum (EP179) is Subset Sum in disguise: with a positive pile P and negative pile N, P - N = target and P + N = total, so P = (total + target) / 2. Not a non-negative integer → 0. Otherwise count subsets summing to P with dp[c] += dp[c - x], backwards, from dp[0] = 1.

Shape C: LIS (looks back at every earlier i)

dp = [1] * n                        # dp[i] = longest increasing subsequence ENDING at i
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)                      # not dp[-1]: the best one can end anywhere

O(n²). The O(n log n) version keeps tails, where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1:

tails = []
for x in nums:
    k = bisect_left(tails, x)
    if k == len(tails): tails.append(x)
    else:               tails[k] = x
return len(tails)

tails is not a subsequence; its length is the answer. EP181 walks both side by side.

Shape D: two sequences or a grid (the state is a pair (i, j))

# LCS: dp[i][j] = LCS of a[:i] and b[:j]; row 0 / col 0 are the EMPTY prefix
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1                # match: extend the diagonal
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])     # drop a char from either

Three neighbours. Unique Paths (EP183) is the same table with two: dp[r][c] = dp[r-1][c] + dp[r][c-1], first row and column all 1.

Shape E: interval DP (the state is a range [l, r], split at every k)

cuts = [0] + sorted(cuts) + [n]
m = len(cuts)
dp = [[0] * m for _ in range(m)]          # dp[l][r] = min cost to cut piece cuts[l]..cuts[r]
for length in range(2, m):                # fill by INCREASING interval length
    for l in range(m - length):
        r = l + length
        dp[l][r] = min(dp[l][k] + dp[k][r] for k in range(l + 1, r)) + (cuts[r] - cuts[l])
return dp[0][m - 1]

dp[l][r] needs every smaller interval inside it, so loop on length, not on l. O(m³). Same shape as Burst Balloons and Matrix Chain; recognising it is most of the work.

The three things that go wrong

1. The state is too small

If f(i) can’t tell you what you need to decide step i, the recurrence is lying. House Robber needs “did I rob i-1?”, which is why it reaches to i-2. Stock with cooldown needs “am I holding?” as a second dimension. A wrong answer on a small case is almost never a loop bug, it’s a missing component of the state. Back to step 1.

2. Forward inner loop on a 1-D knapsack

for c in range(w, W + 1) reuses the current item. Test with one item and a capacity that fits it twice: [w=1, v=1], W=2 must return 1, not 2.

3. The empty prefix at index 0

In a 2-D table, dp[0][*] is the empty prefix, not the first element, so dp[i][j] describes a[:i] and the character you compare is a[i - 1]. Mixing those up presents as “right on the example, wrong on the first hidden test”. Base cases say the empty thing has an answer: Unique Paths’ border of 1s, Target Sum’s dp[0] = 1.

Complexity

Problem	Time	Space
Fibonacci, Stairs, House Robber, Buy Sell Stock	O(n)	O(1) rolling
0/1 Knapsack, Subset Sum, Target Sum	O(n · W)	O(W) one row
LIS (EP180)	O(n²)	O(n)
LIS with bisect (EP181)	O(n log n)	O(n)
LCS	O(m · n)	O(m · n), or O(min(m, n)) rolling
Unique Paths	O(m · n)	O(n) one row
Cut a Stick	O(m³)	O(m²)
the brute force you’re beating	O(2ⁿ)	O(n) stack

The episodes

EP	Problem	Family	The thing it teaches
172	Fibonacci	1-D linear	Recursion → memo → two variables. The four steps, first time.
173	Climbing Stairs	1-D linear	Fibonacci with a story. Spot the recurrence in the prose.
174	House Robber	1-D linear	Take-or-skip. The state must reach back to i-2.
175	0/1 Knapsack	knapsack	The 2-D table and what dp[i][c] means.
176	Tabulation Intro	method	Recursion → table: fill order is reverse call order.
177	0/1 Knapsack Tabulation	knapsack	One row, inner loop backwards, and why.
178	Subset Sum	knapsack	Knapsack with a boolean. dp[c] |= dp[c - x].
179	Target Sum	knapsack	P = (total + target) / 2, then count subsets.
180	LIS	LIS	dp[i] looks at every j < i. Answer is max(dp).
181	LIS Tabulation	LIS	The tails array and bisect_left. O(n log n).
182	LCS	two-sequence	(i, j) state, three neighbours, the empty-prefix row.
183	Unique Paths	grid	LCS’s table with two neighbours and a border of 1s.
184	Buy Sell Stock	1-D linear	Running-min is DP. The hook for the k-transaction variants.
185	Min Cost to Cut a Stick	interval	dp[l][r] over a split k; fill by length.
186	Revision	-	All five shapes, one problem each, from a blank file.

What “knowing this in your sleep” means

1. What is the state, in one sentence? (“dp[i][c] is the best value using the first i items with capacity c.” Can’t say it, stop typing.)
2. What does index 0 mean? (“Nothing chosen yet”, not the first element. One way to make zero.)
3. Which cells does each cell read, and so what’s the fill order? (Look-back-two → left to right. Interval → by increasing length. Knapsack row → backwards.)
4. Why backwards on the 1-D knapsack? (So dp[c - w] still holds the previous row and the item is used at most once.)
5. Which of the five shapes is this, and when is it not DP at all? (Linear, knapsack, LIS, two-sequence, interval. Full list wanted → backtracking. Safe local choice → greedy.)