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

Core idea: A word can only chain onto a shorter word, so if you process words from shortest to longest, every possible predecessor is already solved — and you find a word's predecessors by deleting one character from it in every position.

Problem, rephrased

Imagine you maintain the changelog of a configuration key whose name kept growing one character at a time across releases: a → ab → bda → bdca. Each release inserted exactly one character somewhere into the previous name (front, middle, or back) — never two, never zero. Given a pile of historical names, you want the longest evolution chain you can reconstruct: a sequence of names where each is the immediate predecessor of the next.

Formally (LeetCode 1048): word A is a predecessor of word B if you can insert exactly one character anywhere in A to get B — equivalently, len(B) == len(A) + 1 and deleting one character from B (at some position) yields A. No reordering of the existing letters is allowed. A word chain is a sequence w1, w2, ..., wk where each wi is a predecessor of w(i+1). Return the length of the longest such chain you can build from the given list. A single word is a chain of length 1.

Input words Output A longest chain
["a","b","ba","bca","bda","bdca"] 4 a → ba → bda → bdca
["xbc","pcxbcf","xb","cxbc","pcxbc"] 5 xb → xbc → cxbc → pcxbc → pcxbcf
["abcd","dbqca"] 1 neither chains onto the other → just one word

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.