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.

💡 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

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

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