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

Coin Change

Core idea: Build the answer for every amount from 0 up to the target, smallest first. To make amount a with the fewest coins, try every coin c as the last coin you place: that leaves the sub-amount a - c, whose best answer you already computed. So dp[a] = 1 + min over coins c of dp[a - c]. Seed dp[0] = 0 (zero coins make zero) and treat unreachable amounts as ∞. Because you may reuse each coin freely, this is the unbounded knapsack — there's no "used it already" state, just the amount left to cover.

Problem, rephrased

You run the till at a corner shop. You have an unlimited supply of coins in a fixed set of denominations — say [1, 3, 4] units. A customer needs exactly amount units of change. You want to hand it over using the fewest coins possible (lighter pocket, fewer to count).

Return that minimum coin count. If no combination of your denominations sums to exactly amount, return -1.

coins = [1, 3, 4]      amount = 6

   6  =  3 + 3            ->  2 coins   ✅ fewest
   6  =  4 + 1 + 1        ->  3 coins
   6  =  1 + 1 + 1 + 3    ->  4 coins
   6  =  1 * 6            ->  6 coins

The answer is 2 (3 + 3). Notice the greedy instinct — "grab the biggest coin that fits" — would take 4, then 1 + 1, landing on 3 coins. That's wrong, and that wrongness is the whole reason this is a DP problem.

Inputs / outputs

coins amount fewest coins how
[1, 2, 5] 11 3 5 + 5 + 1
[1, 3, 4] 6 2 3 + 3 (greedy fails here)
[2] 3 -1 odd target, only even coins
[1, 2, 5] 0 0 no coins needed
[5] 5 1 a single coin

You return one integer: the minimum count, or -1 for impossible.

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.