Week 15 — Bitmask & Game DP
Theme: Move beyond standard 2D string DPs into the harder DP archetypes — reverse-direction DP, multi-agent simultaneous DP, adversarial game DP, and bitmask DP over subsets. These are the patterns that distinguish Senior from Staff at the FAANG bar.
Daily schedule
| Day | Problem | LC # | Difficulty | Key archetype |
|---|---|---|---|---|
| Mon | p76 — Dungeon Game | 174 | Hard | Reverse DP — fill from goal back to start |
| Tue | p77 — Strange Printer | 664 | Hard | Interval DP — split on shared endpoints |
| Wed | p78 — Cherry Pickup | 741 | Hard | Multi-agent DP — two simultaneous walks |
| Thu | p79 — Stone Game II | 1140 | Medium-Hard | Game DP — minimax over suffix + parameter M |
| Fri | p80 — Number of Ways to Wear Different Hats | 1434 | Hard | Bitmask DP — flip subject (iterate hats, not people) |
Readiness gate (Friday)
- Articulate why Dungeon Game must be filled from bottom-right to top-left.
- State the Strange Printer “merge shared endpoints” optimization.
- Explain why Cherry Pickup uses one DP with two agents walking simultaneously (not two separate path DPs).
- For Stone Game II, write the minimax recurrence and explain why the suffix-sum + max-of-min structure works.
- For Hats problem, articulate why iterating hats × people-masks (40 × 2¹⁰) is feasible while iterating people × hat-masks (10 × 2⁴⁰) is not.
Why these together
Each problem here breaks a habit formed by easier DPs:
- Dungeon Game — habit of “fill from origin” is wrong; reverse fill is mandatory.
- Strange Printer — natural recurrence is O(n⁴); the “skip k if s[k]==s[i]” insight cuts it to O(n³).
- Cherry Pickup — habit of “find path A, then path B” is wrong; both paths must be considered simultaneously to avoid double-counting cherries.
- Stone Game II — habit of “iterate left-to-right” yields nothing; must iterate suffix-first.
- Hats — habit of “bitmask the obvious set” is wrong; pick the smaller set (people, not hats) as the state.
These five together form the DP archetype recognition pack — by Friday, the candidate should be able to classify a novel DP by archetype within 60 seconds of reading.