DP Mastery Ladder

What This Ladder Trains: Dynamic programming from simple recurrences to advanced optimization. You'll progress through 1D DP, knapsack variants, multi-state DP, bitmask DP, tree DP, and DP with data structure acceleration. By the end, you should confidently identify optimal substructure, design states and transitions, and choose the right optimization technique.

Quick Revisit

• SKILL FOCUS: DP mastery -- 1D recurrences through bitmask and tree DP
• DIFFICULTY: 1200--2000
• PROBLEMS: 15
• PREREQUISITE: DP Thinking Framework

---

Contents

• Warm-Up (1200-1400)
• Core (1400-1600)
• Advanced (1600-1900)
• How to Use This Ladder

---

Warm-Up (1200-1400)

Simple 1D recurrences and basic state transitions. Focus on defining dp[i] correctly.

If problems in this tier fail, the issue is almost always state definition — what does dp[i] mean exactly, and why is it sufficient information to extend to dp[i+1]? If you can't write a precise English sentence for dp[i], you don't have the state yet.

#	Problem	Rating	Hint
1	Cut Ribbon	1300	Hint Coin-change variant: dp[len] = max pieces using the three given ribbon sizes.
2	Vacations	1400	Hint Track dp[i][last] where last in {rest, gym, contest} -- skip repeated or unavailable activities.
3	Orac and Models	1400	Hint For each index i, try all multiples j of i -- dp[j] = max(dp[j], dp[i]+1) when a[j] > a[i].
4	Boredom	1500	Hint House-robber on values: taking k forbids k-1 and k+1. Aggregate counts, then DP on sorted values.
5	Tetrahedron	1500	Hint dp[step][face] with 4 faces. By symmetry only 2 distinct states: "at vertex D" vs "not at D."

If you struggled here, review Chapter 4: Dynamic Programming -- especially 1D recurrences and state design.

---

Core (1400-1600)

Knapsack variants, multi-constraint DP, and 2D state spaces.

If problems in this tier fail, the issue is usually transition design — you have a state but don't see all the ways to reach dp[i][j] (or you're double-counting). Several entries here look like they could be greedy; before settling on DP, sanity-check against the DP vs Greedy Guide — guessing wrong on this choice is the most common stall in this band.

#	Problem	Rating	Hint
6	Sleeping Schedule	1500	Hint dp[i][time_mod_h] = max good sleeps. Two transitions: sleep a[i] or a[i]-1 hours.
7	Ayoub and Lost Array	1500	Hint dp[i][r] = ways to fill 1..i so the running sum === r (mod 3). Transition over each range's valid values.
8	Air Conditioners	1500	Hint Two DP sweeps (left-to-right, right-to-left). dp[i] = min cooling cost at cell i from any AC.
9	Two Arrays	1600	Hint Count non-decreasing arrays a[1..m] <= b[1..m] reversed. Reduce to choosing 2m values -- stars and bars.
10	Slime	1600	Hint Track sign of each element after merges. Answer = total absolute sum, minus adjustment when all signs agree.

If you struggled here, review Chapter 4: Dynamic Programming -- knapsack section and the transition-design checklist.

---

Advanced (1600-1900)

Bitmask DP, tree DP, and DP with data structure optimization.

If problems in this tier fail, the issue is usually state-space ordering or compression — you have the right transitions but visit them in an order that breaks dependencies, or your state has redundant dimensions. One entry below is a deliberate misdirection: not every hard sequence problem is DP. Watch for it.

#	Problem	Rating	Hint
11	Consecutive Subsequence	1700	Hint LIS variant where consecutive elements differ by exactly 1. Use a map: dp[val] = longest ending at val.
12	Caesar's Legions	1700	Hint dp[i][j][last][run]: i,j = soldiers used per type, last = type placed, run = consecutive count of last.
13	Kefa and Dishes	1800	Hint Bitmask DP: dp[mask][last] = max satisfaction eating dishes in mask, ending with dish last.
14	Robot Collisions	2000	Hint (note: this one is not DP) Deliberate misclassification check: this looks DP-shaped but the solution is parity grouping plus a stack to match R-moving with L-moving robots. If you spent 20+ minutes trying to design a DP state, that's the lesson — when the structure has independent groups with greedy matching, DP is the wrong tool.
15	Subsequences of Length Two	2000	Hint dp[i][cnt] where cnt = occurrences of s[0] so far. Transition: change a[i] to s[0] or s[1] for max matches.

If you struggled here, review Chapter 4: Dynamic Programming -- bitmask DP and tree DP -- and Chapter 9: Offline Techniques for DP optimization.

---

How to Use This Ladder

1. Work top-to-bottom. Problems within each tier are ordered by difficulty.
2. Time-box: 30 min for Warm-Up, 45 min for Core, 60 min for Advanced. Click the hint if stuck, then try 15 more minutes.
3. After solving (or giving up), read the editorial and at least one accepted solution.
4. Track weak spots. If knapsack problems trip you up, supplement with 3-5 more from that tag before continuing.
5. Don't skip tiers. Even if Warm-Up feels easy, solve them quickly to confirm your foundation -- speed matters.

Progression Check

• [ ] Warm-Up: solved >= 4/5 without hints
• [ ] Core: solved >= 3/5 within time limits
• [ ] Advanced: attempted all 5, solved >= 2 (with or without hints)
• [ ] Can explain the state and transition for every problem you solved

---

See also: DP Thinking Framework | DP vs Greedy Guide | Rating ladders