Week 13: 1-D Dynamic Programming

Pattern family: Dynamic Programming · Time budget: 14 hours · Prerequisites: Weeks 1 through 12 done, with recursion (Week 7), memoization with lru_cache, and bisect (Week 5) fresh. · Cold-revisit obligation: Course Schedule, Find Median from Data Stream.

Overview

Dynamic programming is one pattern with one disciplined recipe, not a bag of tricks. The whole idea: a problem has a small number of distinct subproblems, those subproblems overlap (the same one is needed many times), and the answer to a larger subproblem is built from a few smaller ones. When that is true, you compute each subproblem once, store it, and reuse it. The exponential blow-up of naive recursion collapses into a linear or quadratic table.

The hard part is not the code; it is naming the state. Once you can say in one sentence “dp[i] is the answer for the prefix ending at i” (or “the fewest coins to make amount i”, or “the number of ways to reach step i”), the transition usually writes itself, and the complexity follows from the size of the table times the cost per cell. Most of this week is training the move that fires before any code: catch the words “number of ways”, “longest / shortest ending at i”, or “minimum cost to reach state X”, and reach for a dp array.

flowchart TD
    Q["Read the problem"] --> A{"Are there overlapping<br/>subproblems, and does the<br/>answer for one state build<br/>from a few smaller states?"}
    A -->|yes| B{"Can I name the state<br/>as one index: dp[i]?"}
    A -->|no| G["Probably greedy, a single pass,<br/>or a different pattern.<br/>Keep reading the cues."]
    B -->|"yes, one index"| H["1-D DP: define dp[i],<br/>the transition, the base case,<br/>the order, the answer cell."]
    B -->|"no, I need two indices"| W["That is 2-D DP (Week 14):<br/>dp[i][j]. Note it and move on."]

Notice: the decision happens before you code, and it has two beats. First, is this DP at all (overlapping subproblems)? Second, does one index capture the state? Naming the state out loud (principle 1) is what makes this diagram fire under pressure.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the prior-week tools that 1-D DP leans on hardest.

  1. From Week 7 and the refresher: what does @lru_cache(maxsize=None) do to a recursive function, and why must its arguments be hashable?
  2. From the refresher: what does [float('inf')] * n build, and why is float('inf') the natural starting value for a “minimum cost” table?
  3. From Week 5: what is the difference between bisect.bisect_left(a, x) and bisect.bisect_right(a, x) on a sorted list a?
Check your recall 1. `@lru_cache(maxsize=None)` caches the return value for each distinct set of arguments, so a repeated call with the same arguments returns the stored result instead of recomputing. That is exactly top-down DP: it turns overlapping subproblems from exponential to linear-in-the-number-of-states. The arguments must be hashable because they are used as dictionary keys in the cache, so you pass tuples and ints, never lists. 2. `[float('inf')] * n` builds a list of `n` copies of positive infinity. For a "minimum cost" table you want every unknown cell to start as "impossible / not yet reached", and `float('inf')` is larger than any real candidate, so `min(current, candidate)` correctly replaces it the first time a real value appears. A cell still equal to `float('inf')` at the end means "unreachable". 3. `bisect_left(a, x)` returns the leftmost index where `x` could be inserted to keep `a` sorted (before any elements equal to `x`); `bisect_right(a, x)` returns the rightmost such index (after any equal elements). `bisect_left` answers "first index with value greater than or equal to `x`", which is the one the LIS tails trick uses.

Learning objectives

By the end of this week you can:

  • Recognize the DP cue (overlapping subproblems, a state that builds from smaller states) and reach for a dp array without being told.
  • Define the state precisely: write the one sentence “dp[i] is …” that every correct DP solution starts from.
  • Construct a bottom-up tabulation from a recurrence, and the equivalent top-down memoization, for the same problem.
  • Analyze the time and space complexity from the table size and the per-cell work, and say what dominates at scale.
  • Distinguish top-down memoization from bottom-up tabulation, and 1-D DP from the 2-D DP that begins next week.
  • Defend every line of each solution you commit, from memory, with no AI open, including why the iteration order is correct.

Recognition cue

“Overlapping subproblems, and the decision at each position depends on prior decisions” almost always means dynamic programming. In a problem statement, the surface phrases are “number of ways”, “longest / shortest / largest … ending at i”, “minimum / maximum cost to reach state X”, and “can I form / partition this”. The deeper tell is that a brute-force recursion would recompute the same subproblem many times; the moment you notice that repetition, you are looking at DP.

Core concepts to internalize this week

  • The state is the whole game. Before anything else, write one sentence: “dp[i] is the [answer] for [the subproblem indexed by i].” If you cannot write that sentence, you do not yet understand the problem, and no code will save you. Everything below depends on a correct state definition.
  • The transition (recurrence). Given the state, how does dp[i] build from earlier cells? For Climbing Stairs it is dp[i] = dp[i-1] + dp[i-2]. For Coin Change it is dp[a] = 1 + min(dp[a - c]) over usable coins c. The transition is a relation between cells, not code yet.
  • Base case and iteration order. A recurrence needs a starting point (dp[0], sometimes dp[1]), and you must compute cells in an order where every cell a transition reads is already filled. Bottom-up means smallest subproblems first.
  • Answer extraction. The answer is a specific cell or an aggregate over cells. Sometimes it is dp[n]; sometimes it is max(dp) (LIS, where the longest run can end anywhere). Knowing which is part of defining the state.
  • Top-down vs bottom-up. Top-down is the natural recursion plus @lru_cache: write the recurrence as a function, cache it. Bottom-up fills the table iteratively from the base case. They have the same complexity; bottom-up avoids recursion-depth limits and makes space optimization obvious.
  • Space optimization to rolling variables. When dp[i] only reads the last one or two cells, you do not need the whole array; two variables suffice, dropping space from O(n) to O(1). Climbing Stairs and House Robber both reduce to this. Maximum Subarray is the cleanest example of the shape: the state is “the best contiguous run that ends right here”, each position’s answer is built from the single prior position’s answer, and the global answer is the largest such running value, so the whole thing collapses to a rolling variable in O(1) space.
  • Unbounded vs 0/1 knapsack. In Coin Change you may reuse a coin any number of times (unbounded), so the inner loop lets the same coin contribute repeatedly. In a 0/1 problem each item is used at most once, which changes the loop order. Knowing which framing a problem is determines the loop.
  • The O(n log n) LIS trick. Longest Increasing Subsequence has a clean O(n^2) DP (dp[i] is the longest increasing subsequence ending at i). It also has an O(n log n) method: maintain a tails array where tails[k] is the smallest possible tail of an increasing subsequence of length k+1, and place each number with bisect_left. The tails array is not itself a valid subsequence, but its length is the answer.

Common misconception. “Dynamic programming is a clever, problem-specific trick I have to invent fresh each time.” Reality. It is one recipe applied over and over: define the state, write the transition, set the base case, choose the order, extract the answer. The creativity is almost entirely in the first step (naming the state). Once you treat DP as a checklist rather than an inspiration, most 1-D problems take the same shape, and the ones that feel hard are usually ones where you skipped step one.

Heavy concept ahead. The five-step DP framework is the load-bearing idea of this week and the next, so internalize it deliberately, in this order, every time:

  1. State. “dp[i] is …” in one sentence.
  2. Transition. How dp[i] is built from smaller cells (the recurrence).
  3. Base case. The smallest subproblem(s) you can answer directly.
  4. Order of computation. The sweep that guarantees every cell is filled before it is read.
  5. Answer extraction. Which cell or aggregate is the final answer. Write these five down, in words, for every DP problem this week before you write any code. The Pattern Card asks for them; the canonical deep-dive walks them; the debrief checks them. Skipping a step is the single most common way DP solutions come out wrong.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday.

  • List initialization for tables: [0] * n for counts, [float('inf')] * (n + 1) for a minimum-cost table, [False] * (n + 1) for a reachability table. (Note [0] * n is safe for a flat 1-D list; the aliasing trap only bites 2-D lists, which arrive in Week 14.)
  • functools.lru_cache(maxsize=None) as a decorator to memoize a recursive top-down solution; remember the arguments must be hashable.
  • Rolling-variable space optimization: prev, curr = curr, prev + curr, updating one or two variables instead of holding the whole array.
  • bisect.bisect_left(tails, x) for the O(n log n) LIS tails array.
  • min(...) and max(...) over a running candidate, often seeded with float('inf') or 0.
  • A set(word_dict) for O(1) membership when a problem hands you a word list (Word Break).
  • String slicing s[j:i] to pull a substring (it copies, so the slice itself costs O(length)).

These are tools you are allowed to know cold in an interview. The pattern (the state, the transition, why the order is correct) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/1d-dynamic-programming.md. It must contain:

  • The recognition cue, in your own words.
  • The algorithmic skeleton in pseudocode (the five-step framework reduced to a template you can reuse).
  • Time and space complexity, general form (table size times per-cell work; plus the space win from rolling variables).
  • Three edge cases (empty input, a single element, and a target of zero or an unreachable target are good starts).
  • One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: Coin Change (https://leetcode.com/problems/coin-change/)

Coin Change is this course’s home for the five-step DP framework and the unbounded-knapsack framing. The full guided walk-through, with the state definition, the transition, the iteration order, and the exact complexity, is in canonical/coin-change.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think, and stops short of code you could paste.

Practice set

Five problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead.

  1. Climbing Stairs (practice/climbing-stairs/). The smallest possible DP: count the ways to reach the top. This is the problem that shows you DP and the Fibonacci recurrence are the same shape.
  2. House Robber (practice/house-robber/). A yes-or-no choice at each position, where taking one element forecloses its neighbor.
  3. Longest Increasing Subsequence (practice/longest-increasing-subsequence/). “Longest … ending at i” over a sequence; there is a straightforward version and a faster one worth finding.
  4. Word Break (practice/word-break/). Can a string be split into pieces drawn from a dictionary? A reachability question over the prefixes of the string.
  5. Maximum Subarray (practice/maximum-subarray/). The largest sum of any contiguous run. The cleanest “best run ending at i, built from the best ending at i-1” shape, and it reduces to a single rolling variable.

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

  1. Pattern Card is written (you did this Monday).
  2. Name the pattern aloud and write your approach as a plain-English comment before any code.
  3. Struggle floor: 25 minutes unaided.
  4. Hint ladder if needed: six rungs, one per ask.
  5. Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

  • Explain it back: describe the five-step DP framework to a peer who has only done arrays and graphs so far, in five sentences (one per step).
  • Connect: Climbing Stairs and the Fibonacci sequence have the same recurrence. What is the “state” in each, and why does the rolling-variable optimization apply to both?
  • Monitor: which step of the five (state, transition, base case, order, answer) is still the one you fumble? Write the one sentence that would steady it.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

  1. State the five steps of the DP framework in order, in your own words.
  2. For Coin Change, what is the state dp[a], what is the transition, and how do you report “amount cannot be made”?
  3. Top-down memoization and bottom-up tabulation for the same problem have the same time complexity. Name one concrete reason you might still prefer bottom-up.
  4. ⟲ From Week 5: in the O(n log n) LIS method you place each number with bisect_left into a tails array. Why bisect_left and not bisect_right, and what does tails[k] mean?
  5. ⟲ From Week 7 and the refresher: why must the arguments to an @lru_cached function be hashable, and what goes wrong if you try to cache a function that takes a list?
Answer key 1. State (one sentence: "`dp[i]` is ..."), transition (how `dp[i]` builds from smaller cells), base case (the smallest subproblem you answer directly), order of computation (fill cells so every cell is ready before it is read), answer extraction (which cell or aggregate is the result). 2. `dp[a]` is the fewest coins that sum to amount `a`. The transition is `dp[a] = 1 + min(dp[a - c])` over every coin `c` with `c <= a` and `dp[a - c]` reachable. You report impossibility by starting the table at `float('inf')` (with `dp[0] = 0`) and, at the end, returning -1 if `dp[amount]` is still `float('inf')`. 3. Any one of: bottom-up has no recursion-depth limit (top-down can hit `RecursionError` on large n); bottom-up makes the rolling-variable space optimization obvious; bottom-up avoids per-call function overhead. The complexity is the same; the engineering differs. 4. `tails[k]` is the smallest possible tail value of any increasing subsequence of length `k + 1`. You use `bisect_left` so that a value equal to an existing tail replaces it (keeping the subsequence strictly increasing) rather than extending the array; using `bisect_right` would admit equal elements and overcount on inputs with duplicates. 5. `lru_cache` stores results in a dictionary keyed by the call's arguments, and dictionary keys must be hashable. A `list` is mutable and therefore unhashable, so passing one raises `TypeError`; you convert to a tuple (or redesign the state to use indices) before caching.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each.

  1. Course Schedule (Week 11, Graphs). A blind re-solve. Do not look at which pattern it is until you have named it yourself; recognizing it cold is the point.
  2. Find Median from Data Stream (Week 8, Heap and Priority Queue). A blind re-solve, same rules.

Neither is a DP problem, and that is deliberate: the cold revisit trains recognition across the whole course, not just this week’s pattern. Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

  • Pattern Card complete at .tutor/pattern-cards/1d-dynamic-programming.md, including the war-story field.
  • Canonical deep-dive done: Coin Change implemented yourself (bottom-up, and ideally the top-down memoized version too), with your short debrief (in your work repo).
  • Five practice problems solved, each with a five-question debrief in its commit message.
  • .tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
  • .tutor/progress.md updated to “Week 13 complete; ready for Week 14.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 14 until all five are present.

Resources

Free, no account required:

  • [Article] Dynamic programming, the idea: https://en.wikipedia.org/wiki/Dynamic_programming
  • [Article] Memoization: https://en.wikipedia.org/wiki/Memoization
  • [Docs] Python functools.lru_cache: https://docs.python.org/3/library/functools.html#functools.lru_cache
  • [Docs] Python bisect: https://docs.python.org/3/library/bisect.html

Table of contents