08 — Phase 4 Exit Criteria & Projects

Phase 4 | Week 30 | Feb 22, 2027

This is the checkpoint. Phase 4 is the hardest phase in the entire roadmap — not because the mechanics are complicated, but because DP requires a level of pattern fluency that only comes from doing the work. The exit criteria below are binary: you either can or you can’t. No partial credit on these. If you can’t pass them, go back and identify the specific pattern that’s failing, then drill that one more week.

Exit Criteria

These are the three questions you need to answer “yes” to before starting Phase 5.

Criterion 1: Pattern Recognition in ≤ 3 Minutes

Given an unseen DP problem description, correctly identify the DP pattern (1D linear, 2D grid, knapsack, interval, subsequence, tree, or bitmask) within 3 minutes, without writing any code.

How to test yourself: Pick any DP problem on LeetCode you haven’t seen before. Set a 3-minute timer. Write down: (a) the pattern name, (b) what dp[...] represents, (c) the transition formula in words. No code required — just the mental model.

You pass if: You get the pattern right on 8 out of 10 random problems. Misidentifying 2 is acceptable (especially interval vs. 1D, which can be ambiguous). Consistently misidentifying the same pattern means go back to that file and drill.

Common failure modes at this stage:

  • Confusing knapsack 0/1 vs. unbounded (they look identical until you check reuse rules)

  • Not recognizing bitmask DP because you forgot to check n ≤ 20

  • Calling interval DP “2D DP” because the table is 2D (technically true but pattern is different)

Criterion 2: State + Transition Design for Medium Problems

Given any LeetCode Medium DP problem, correctly define the state (what dp[i] or dp[i][j] represents) and the complete transition formula within 15 minutes.

How to test yourself: Pick 5 random Medium DP problems on LeetCode. For each one, write the state definition and transition formula on paper (or a text file) before looking at any solution. Then verify.

You pass if: You get the state and transition correct for 4 out of 5 (80%). Getting the state definition wrong and correcting it after recognizing the transition doesn’t work still counts as a miss — the state is the upstream decision.

Why this matters: In a FAANG interview, you have 45 minutes total. You cannot afford to spend 20 minutes figuring out the state. The state should come in the first 5 minutes of problem analysis.

Criterion 3: Solve LeetCode Hard DP in ≤ 60 Minutes

Independently solve at least 3 LeetCode Hard DP problems — specifically House Robber III (337), Burst Balloons (312), and Edit Distance (72) — in under 60 minutes each. “Independently” means no hints, no solution, no discussion tab.

How to test: Close all references. Open LeetCode. Set a 60-minute timer. Code from scratch.

You pass if: You solve all 3. If Edit Distance runs over 60 minutes, that’s a red flag — it’s the most mechanical of the three and you should be able to derive it in 20-30 minutes by now.

Note: Burst Balloons is genuinely hard. If it takes you 55 minutes, that’s fine. If it takes you 90 minutes, go back to 05_interval_and_subsequence_dp.md and drill interval DP for one more week.

Projects

Three deliverables. These are not optional extras — they are the mechanism by which you convert “I’ve read about DP” into “I have internalized DP.”

Project 1: DP Pattern Taxonomy Notebook

What to build: A personal reference document (markdown, Notion, paper — whatever you actually use) containing 1 solved example per pattern. For each example:

  • State definition: “dp[i] represents…”

  • Transition formula (written out, not copy-pasted from LeetCode)

  • Base cases

  • Answer location

  • Space optimization (if applicable)

One example per pattern = 7 entries minimum. Choose problems you solved independently, not ones you read solutions to. The whole point is that you can reproduce the derivation from memory.

Acceptance criteria: Given the notebook closed, you can reproduce the state definition and transition for any of the 7 patterns from memory in under 3 minutes. Have a friend quiz you, or quiz yourself a week after writing it.

Suggested problems per pattern:

  • 1D Linear: House Robber (198)

  • 2D Grid: Edit Distance (72)

  • Knapsack: Coin Change (322) for 0/1, Coin Change II (518) for unbounded

  • Interval: Burst Balloons (312)

  • Subsequence: LIS (300) — include O(n log n) version

  • Tree: House Robber III (337)

  • Bitmask: Minimum XOR Sum (1879)

Project 2: LeetCode 30-Problem DP Sprint

What to build: Solve 30 DP problems:

  • 5 Easy

  • 18 Medium

  • 7 Hard

Acceptance criteria: ≥ 70% independent solves (21 out of 30). “Independent” means you arrive at the correct state and transition yourself, even if you need to look up syntax. Looking at a hint before writing anything disqualifies the problem.

70% is the honest number. DP is legitimately hard. Forcing 100% independence leads to discouragement and delusional standards. 70% with honest assessment is more valuable than 95% with “I just needed one small hint.”

Tracking: Maintain a simple table:

| Problem | Pattern | Independent? | Time (min) | Notes |
|---|---|---|---|---|
| House Robber (198) | 1D Linear | Yes | 12 | |
| Burst Balloons (312) | Interval | No | 55+ | Looked at hint after 40min |

Suggested problem list by pattern: Use the practice problems from files 02-06 as your starting set. 30 problems across 7 patterns means ~4-5 per pattern. Prioritize the ones flagged as canonical.

Project 3: “Explain the Pattern” Document

What to build: Write an explanation of 3 DP patterns aimed at a complete beginner — someone who knows Python and has done 10 LeetCode Easys but has never seen DP.

Pick any 3 patterns. For each one:

  1. What problem does this pattern solve? (1 paragraph, no jargon)

  2. A concrete, small example walked step-by-step

  3. The general template with annotations

  4. One common mistake and why it happens

Acceptance criteria: Show it to one other person (colleague, friend, anyone). If they say “I think I understand how to start a problem like this,” you pass. If they say “I’m confused,” identify where the explanation broke down and fix it.

Why this project exists: The Feynman technique is a cliché because it works. Writing an explanation forces you to identify every gap in your understanding. You cannot fake it when you have to explain the transition logic in plain English without using DP jargon.

Format: Anything you’ll actually maintain. A Notion doc, a GitHub gist, a markdown file in this repo, a blog post, a message to a study partner.

Timeline Sanity Check

By the end of Week 30 (Feb 22, 2027), you should have:

  • Worked through all 7 files in this phase

  • Attempted 30+ DP problems

  • Built the taxonomy notebook

  • Written the explanation document

  • Passed all 3 exit criteria

If you’re behind: compress the sprint, don’t skip exit criteria. You can defer Project 3 by a week. You cannot defer the ability to design DP state — that’s the prerequisite for Phase 5.

What to Do If You’re Stuck

Being stuck on DP is normal. Here’s a prioritized debugging protocol:

  1. Can’t figure out the state? Re-read the problem statement. Write out small examples by hand. What changes as the input grows? The thing that changes is often your state variable.

  2. Have the state but transition is wrong? Verify on a small example (n=3 or n=4). Trace through your transition formula manually. The bug will reveal itself.

  3. Passes small examples but wrong on large inputs? Usually an initialization bug (wrong base case), an off-by-one in table dimensions, or wrong loop direction for knapsack.

  4. Can’t get started at all? Write the brute-force recursive solution first, ignoring complexity. Then add memoization. If that’s correct, convert to bottom-up. The structure is always there — memoization will expose it.

  5. Still stuck after 45 minutes? Read the solution. But before you do, write down your current wrong state definition and compare it to the correct one. Understanding what you had wrong is more valuable than the correct solution.

Transition to Phase 5

Once you pass exit criteria, Phase 5 awaits. The mental shift:

DP asked “can I express the answer to a big problem in terms of answers to smaller problems?” Phase 5 asks “what data structure lets me answer this query in O(log n) instead of O(n)?” Different paradigm, but the rigor you built in DP — thinking precisely about state, transitions, and invariants — directly transfers.

Phase 5 starts Feb 23, 2027.