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

Min Cost Climbing Stairs

Core idea: Dynamic programming is just remembering the answers to overlapping subproblems instead of recomputing them. The cheapest way to reach step i only depends on the two steps you could have jumped from — so once you know the cost to reach every earlier step, the cost to reach i is one tiny addition. Solve each step once, reuse it forever.

This is your first dynamic-programming lesson, so we're going to go slow and build the method, not just the answer. By the end you'll have a 4-step recipe you can point at almost any "1D DP" problem.

Problem, rephrased

You're at the bottom of a staircase. Each stair i charges you a toll cost[i] the moment you step onto it. From any stair you may climb 1 step or 2 steps. You're allowed to start — for free — on either stair 0 or stair 1. Your goal is to reach the top of the staircase, which is the floor one past the last stair (it has no toll).

Minimize the total tolls you pay.

        cost = [10, 15, 20]

  stair:   0     1     2    (top)
  toll:   10    15    20     0
           ^     ^            ^
        start    start here   reach here, past the last stair

Start on stair 1 (pay 15), jump 2 to the top (past stair 2). Total = 15. That beats starting on stair 0.

Inputs / outputs

cost best plan answer
[10, 15, 20] start at 1 (15), jump 2 to top 15
[1,100,1,1,1,100,1,1,100,1] hop the cheap 1's, skip the 100's 6
[0, 0] start at 0, jump 2 to top (or start at 1) 0
[5, 10] start at 1 (10)? no — start at 0 (5), jump 2 5

You pay for every stair you land on; you never pay for the top because there's no stair there.

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.