Day 74 — Mock: 3 DP problems, 60 minutes

60 minutes · mock day · dynamic programming

Tonight's goal: solve one 1-D DP problem, one 2-D/two-strings DP problem, and one free-choice DP problem under a strict timer.

Tonight's protocol

Use the mock-day process: speak first, code honestly, compare after the timer.

  1. 0:00–0:04 — Warm up. Answer the MCQs below. Read explanations only for misses.
  2. 0:04–0:05 — Pick the set. Choose exactly one 1-D problem, one 2-D/two-strings problem, and one free-choice problem from the menu.
  3. 0:05–0:23 — Problem 1. Before coding, state all four DP answers aloud: state, transition, base case, answer location.
  4. 0:23–0:41 — Problem 2. Repeat the same four-answer checkpoint before the first line of code.
  5. 0:41–0:59 — Problem 3. If stuck after 12 minutes, read only the pattern name in the menu and use the final 6 minutes.
  6. 0:59–1:00 — Gate. Mark pass or fail below. Compare after the timer, not during it.

The problem menu

Pick one from each row. If choice takes more than 60 seconds, use the first link in that row.

SlotChoose one problemPattern name
1-D DP House Robber / Climbing Stairs / Decode Ways DP II: take it or skip it / DP I: the four questions / DP VIII: Counting With Constraints
2-D/two-strings Longest Common Subsequence / Edit Distance DP VI: two strings, one grid / DP VII: edit distance
Free choice Coin Change / Longest Increasing Subsequence / Partition Equal Subset Sum / Word Break / Burst Balloons DP III: fewest coins / DP IV: longest increasing subsequence / DP V: 0/1 knapsack / DP IX: Segmentable Prefixes / DP X: interval DP

For every selected problem, say these four answers aloud before coding: what the state means, how it comes from smaller states, the base case, and where the final answer lives.

Warm-up MCQs

1. Before coding any DP problem, which checklist must be spoken?

2. A current item can be used or skipped. Which phrase matches House Robber?

3. In Coin Change, what should dp[amount] store?

4. In LIS, what does dp[i] mean?

5. Two strings, current characters match. Which move is the LCS invariant?

6. Burst Balloons feels tangled because neighbors change. Which choice untangles the interval?

Self-check gate

Pass tonight ifFailure path
You attempted all three timed slots, spoke the four DP answers before each problem, and got at least two problems accepted or clearly correct on sample tests. For any failed problem, write WA: <root cause>, add that exact problem to the next revision list, and re-solve it from a blank file with no hints.
If a solution failed, you can still explain which answer broke: state, transition, base case, or answer location. If you cannot name the broken answer, compare after the timer and write the missing invariant as the first revision note.