</> MAANG.io
Sign in
Level101201301
coding interview · 101

Foundations

Master coding interviews with comprehensive coverage of data structures, algorithms, and problem-solving techniques. Progress from fundamentals to advanced topics with expertly curated content.

0/255 solved 0% complete

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.

flowchart TD A["State dp at i"] --> B["List the choices here"] B --> C["Reuse an earlier solved answer per choice"] C --> D["Keep the best choice"] D --> E["Move to the next state"]

💡 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 shared recurrence: dp[i] = best over choices of combine(dp[i - effect(c)], cost(c)), instantiated for coins, tickets, integer break and string chain

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

Advanced linear DP problem family: Coin Change (min over coins), Min Cost For Tickets (min over passes), Integer Break (max over splits), Longest String Chain (max over predecessors)

  • 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.

Minimum Cost For Tickets

Core idea: Walk forward day by day. On a day you don't travel, the cheapest plan is unchanged — dp[d] = dp[d-1]. On a day you do travel, the cheapest plan must include some pass that covers today, and there are only three kinds; whichever pass you pick "ends" its coverage window here, so its cost rides on top of whatever was optimal before that window started: min(dp[d-1] + cost1, dp[d-7] + cost7, dp[d-30] + cost30). Look back 1, 7, or 30 days, add the matching pass, take the minimum.

Problem, rephrased

Forget the textbook phrasing. Here's the scenario:

You commute on a fixed set of future dates this year — say the days you're scheduled in the office. To ride, you must hold a valid travel pass on each of those days. The transit authority sells three passes:

  • a 1-day pass costing costs[0],
  • a 7-day pass costing costs[1] (covers the day you buy it plus the next 6 days),
  • a 30-day pass costing costs[2] (covers the day you buy it plus the next 29 days).

A pass covers a sliding window of consecutive calendar days starting whenever you activate it. You're given days — a sorted, strictly increasing list of the days you travel (each in 1..365) — and costs. Return the minimum total cost to have valid coverage on every travel day. You never need coverage on days you don't travel, but a multi-day pass bought for one travel day may "spill over" and cover later ones for free.

Input days costs Output Why
[1,4,6,7,8,20] [2,7,15] 11 one 7-day pass on day 1 covers 1–7; 1-day passes for 8 and 20
[1,2,3,4,5,6,7,8,9,…,31] [2,7,15] 17 a 30-day pass blankets the dense run; 1-day for the straggler
[5] [2,7,15] 2 a single travel day — just buy the cheapest single-day option

The travel days are sparse inside the calendar: only a handful of the 365 days matter, but a 7- or 30-day pass bought on one of them can blanket several at once.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.