Advanced Linear DP

What is this?

This is still one-dimensional DP — you move along a single line — but now each answer is found by trying many options and keeping the best one, instead of just reading a fixed neighbor. Picture making change for an amount: to know the fewest coins for 30 cents, you test every coin and reuse the already-solved smaller amounts. Because you remember those smaller answers, you never re-solve them, and this is exactly where being greedy and grabbing the biggest coin first can quietly give the wrong answer.

💡 Fun fact: The U.S. coin system is "canonical," so greedily grabbing the largest coin always works for it — which is exactly why Coin Change feels easy until an interviewer hands you oddball denominations like 1, 3, and 4 and the greedy trick falls apart.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Still one dimension, but now each dp[i] is computed by scanning a set of choices rather than reading one or two fixed neighbors. The transition asks "which coin / which pass / which split / which predecessor do I commit to here?" and takes the best. This is where DP starts to clearly beat greedy — because the locally-best choice is no longer safe.

The shape

The cost of each state rises from O(1) to O(#choices), but the structure is still a single sweep that reuses earlier answers.

The problems

• Coin Change — unbounded knapsack: dp[a] = min(dp[a-c]+1); DP precisely because greedy fails for arbitrary denominations.
• Minimum Cost For Tickets — at each travel day choose which pass (1/7/30-day) to let expire by looking back.
• Integer Break — maximize a product by trying every split point (with the all-3s greedy as the elegant shortcut).
• Longest String Chain — LIS in disguise: order words by length and extend from one-char-shorter predecessors.

Key takeaways

• Each state scans a set of choices and takes the best — the step up from basic linear DP.
• This is the canonical "greedy fails ⇒ use DP" zone (Coin Change is the poster child).
• Order the subproblems so dependencies are solved first (amounts ascending, words by length).
• Recognize disguises — Longest String Chain is LIS; many DPs are old patterns reskinned.
• Why interviewers love it: choosing the right state and choice-set is the heart of DP design.

Start here: Coin Change, then Minimum Cost For Tickets.