60 minutes · Day 67 · mock day · dynamic programming
Tonight's goal: pick two DP problems, optionally a third stretch problem, and make the state, recurrence, base case, and answer location clear before coding.
0:00–0:02 — Pick: choose exactly two problems from the menu. Choose a third only if both pass before minute 45.
0:02–0:05 — Warm up: answer the MCQs below. If one misses, read the explanation and still start the timer.
0:05–0:07 — Speak first: for problem 1, say the pattern name, brute force, recurrence, base case, answer location, and complexity.
0:07–0:25 — Code honestly: write the recurrence as the first editor comment, then code with no solution text.
0:25–0:27 — Stuck rule: if stuck, read only the pattern name from this page, say the recurrence again, and continue.
0:27–0:45 — Problem 2: repeat the same speak-first, recurrence-comment, code-honestly loop.
0:45–0:55 — Stretch or compare: start a third problem only if the first two are accepted; otherwise compare the failed attempt.
0:55–1:00 — Encode: write one note per miss: invariant, bug, or self-check gate to revisit.
The problem menu
Pick two from Days 61–65. For each chosen problem, explain aloud before typing. Your first editor line must be a recurrence comment, such as # recurrence: dp[i] = ....
Source invariant: “Every DP is four answers: what dp[i] means, how it comes from smaller states, the base case, and where the final answer lives. Here: ways(i) = ways(i-1) + ways(i-2).”
2. At each house, what choice must the recurrence compare?
Source invariant: “At each house choose: rob it and add dp[i-2], or skip it and keep dp[i-1] — dp[i] = max(dp[i-1], nums[i] + dp[i-2]).”
3. In Coin Change, what should unreachable amounts do?
Source invariant: “dp[amount] = 1 + the minimum of dp[amount - coin] over every coin; amounts you can never make stay infinite.”
4. A LIS solution returns dp[-1]. What invariant did it forget?
Source invariant: “Define dp[i] as the best subsequence ending exactly at i: one more than the best dp[j] over all j < i with nums[j] < nums[i].”
5. For Partition Equal Subset Sum, why sweep target high to low?
Source invariant: Ask “can some subset hit this exact target?” where target = totalSum/2; each item is usable once, so sweep targets from high to low.
Self-check gate
Pass tonight: two chosen problems have a spoken pattern name, a recurrence comment before code, correct base cases, a correct final answer location, and either an accepted submission or a clear timer-end comparison note.
Fail path: if the recurrence is unclear, the base case is guessed, the LIS answer location is wrong, Coin Change impossible states are not infinite, or 0/1 knapsack sweeps upward, add that failed problem to the next revision list with one root-cause line.
Example note: WA: used upward sweep in Partition, so the current item was reusable.