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

Integer Break

Core idea: To split n for maximum product, decide the first piece j, then ask: is the rest (n - j) better used as one raw chunk, or broken up further? That second question is the same problem on a smaller number — so define dp[i] = best product obtainable by breaking i, build it up from small i, and at each split take max(piece, dp[piece]) on both sides. This is partition DP: the answer for i is the best over all the ways to cut off a first part.

Problem, rephrased

Forget the textbook phrasing. Here's the scenario:

You have n units of a single resource — say n identical hours of factory time — and you must chop them into at least two whole-number lots. Each lot then runs a process whose output equals the lot size, and the lots run in parallel, so the total payoff is the product of the lot sizes. How do you carve up n to make that product as large as possible?

Formally: given an integer n, break it into the sum of at least two positive integers n = a₁ + a₂ + … + aₖ (k ≥ 2), and maximize the product a₁ · a₂ · … · aₖ. Return that maximum product.

Input n Output A split that achieves it
2 1 1 + 1 → 1·1 = 1 (forced to split)
7 12 3 + 4 → 3·4 = 12 (or 3+2+2)
10 36 3 + 3 + 4 → 3·3·4 = 36

Two things make this less trivial than it looks. First, you're forced to split — even n = 2 must become 1 + 1, so the answer can be smaller than n. Second, "at least two parts" is the only constraint; you may use as many parts as you like.

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.