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

Linear DP

What is this?

Linear DP is the simplest flavor of dynamic programming: you walk along a single line — an array, a string, or a number — and each answer dp[i] is built from one or two answers you already worked out just before it. It is exactly like figuring out the cheapest way to reach step i on a staircase once you know the cheapest way to reach the steps below. Because each small answer is reused many times, you store it once instead of recomputing it.

flowchart TD A["Walk along one axis"] --> B["Define dp at index i"] B --> C["Build dp i from a few earlier entries"] C --> D["Set the base cases"] D --> E["Keep only the entries you reread"]

💡 Fun fact: The "counting bits" idea — that the number of 1-bits in i equals the bits in i with its last bit removed, plus that last bit — is so cheap that modern CPUs ship a single popcount instruction to do it in hardware.

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

Core idea: Dynamic programming is just remembering the answers to overlapping subproblems instead of recomputing them. Linear DP is where you learn the method on a single axis: dp[i] answers a question about the first i elements (or the number i), and the recurrence builds dp[i] from a few earlier entries. Master the 4-step method here and every harder DP is a variation.

The 4-step DP method

The 4-step DP method: 1 Subproblem (what does dp[i] mean), 2 Recurrence (how dp[i] uses earlier dp[]), 3 Base cases (the smallest subproblems), 4 Optimize (table to rolling variables, O(1) space)

Every lesson here is the same recurrence expressed four ways — brute recursion, memoized top-down, bottom-up table, and rolling variables. They differ only in what they remember and when.

The problems

Linear DP family tree: dp[i] from earlier entries branches into Min Cost Climbing Stairs (the intro), Word Break (DP over a string prefix), Rotated Digits (state from a sub-number), and Counting Bits (DP riding on bit structure)

  • Min Cost Climbing Stairs — the gentle intro: dp[i] = cost[i] + min(dp[i-1], dp[i-2]); the place to learn the whole method.
  • Word Break — dp[i] = "is the prefix s[:i] segmentable?"; break at the last word.
  • Rotated Digits — a number's verdict composes from dp[i//10] plus its last digit.
  • Counting Bits — dp[i] = dp[i>>1] + (i&1): every number reuses a smaller solved one.

Key takeaways

  • DP = overlapping subproblems + optimal substructure — remember, don't recompute.
  • The recurrence is the whole game; the four implementations just trade memory for clarity.
  • dp[i] over a prefix is the linear template — a string, an array, or a number.
  • Optimize last — once the table works, keep only the few entries the recurrence reads.
  • Why interviewers love it: it reveals whether you can define a subproblem and a transition, the core DP skill.

Start here: Min Cost Climbing Stairs (learn the method), then Word Break.

Core idea: ask one question at every cut point — can the part before this cut be segmented, and is the chunk from there to here a single dictionary word? A position is reachable if some earlier reachable position is one dictionary word behind it. That turns "split the whole string somehow" into a single boolean per prefix, computed left to right.

Problem, rephrased

You're handed a string s and a wordDict — a list of allowed words. Return True if you can chop s into a back-to-back sequence of dictionary words with nothing left over and no gaps, and False otherwise. You may reuse a dictionary word as many times as you like, and you don't have to use every word.

Picture s as a row of letters and wordDict as a box of LEGO bricks, where each brick is stamped with one allowed word. You're trying to tile the whole row using only those bricks, end to end, no overlaps, no overhang. If the bricks happen to cover the row exactly, the answer is True. If you always end up with a sliver you can't fill, it's False.

s wordDict Can it be tiled? A valid split
"leetcode" ["leet", "code"] True leet · code
"applepenapple" ["apple", "pen"] True apple · pen · apple (word reused)
"catsandog" ["cats", "dog", "sand", "and", "cat"] False no tiling reaches the end
"aaaaaaa" ["aaaa", "aaa"] True aaaa · aaa
"" ["x"] True the empty string needs zero words

Notice row 2: apple is used twice — reuse is allowed. And row 3 is the trap: you can place cats/cat/sand/and over the front, but every front placement leaves a tail (og or dog-minus-something) that no brick fills exactly. Local progress is not the same as reaching the end.

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.