Day 66 — Revision: DP basics

revision day · dynamic programming · blank-file recall

Tonight's goal: pick the three weakest DP problems from this menu, then prove you can rebuild the state, transition, base case, and answer location without hints.

Tonight's protocol

Use the revision-day protocol: blank file, no hints, and only run one or two count.

  1. 0:00-0:03 Answer the warm-up MCQs below. If an invariant is fuzzy, mark that problem as weak.
  2. 0:03-0:05 Pick your three weakest problems from the menu. Open a blank file for the first one.
  3. Before each solve recite four sentences: state, transition, base case, answer location. Do this before typing code.
  4. 0:05-0:25 Attempt problem 1 with no notes, no saved code, no video, and no hints.
  5. 0:25-0:45 Attempt problem 2 under the same rule.
  6. 0:45-1:05 Attempt problem 3 under the same rule.
  7. 1:05-1:15 Compare only after the attempts. For every miss, write WA: <root cause> and keep it in the revision queue.

The problem menu

Pick your three weakest. Re-solve from a blank file, no hints. Before each problem, say the four-sentence drill out loud.

ProblemPattern namePre-code drill
Climbing Stairs DP four questions ways to step i; add previous two; ground and first step; answer at dp[n]
House Robber take-or-skip DP best through house i; skip or rob; empty prefix is zero; answer after final house
Coin Change unbounded minimum DP fewest coins for amount a; try every last coin; zero amount needs zero coins; answer at dp[amount]
Longest Increasing Subsequence ending-at-i DP state best subsequence ending at i; attach smaller previous endings; each item alone is one; answer is max(dp)
Partition Equal Subset Sum 0/1 knapsack reachable sums can a subset make sum s; use or skip each item; empty subset makes zero; answer at dp[target]

Warm-up MCQs

1. Which checklist belongs before any DP solve?

2. Which comparison matches House Robber?

3. What must happen to unreachable Coin Change amounts?

4. Which state is precise enough for LIS?

5. Which sweep protects the one-use subset rule?

Self-check gate

Pass tonight only if this is true

All three selected problems pass on run one or run two, and before each solve you can say the state, transition, base case, and answer location without reading the lesson.

If any problem needs a hint, fails after two runs, or has a blurry four-sentence drill, it does not count as revised. Write WA: <root cause>, add that problem to the next revision day, and compare with the source lesson after the attempt.