Algorithms from zero

One-dimensional DP: house robber, climbing stairs, decode ways

Crux The 1D DP pattern: state is a single position i and dp[i] depends on a few earlier cells. House Robber is max(dp[i-1], dp[i-2]+nums[i]); Climbing Stairs is Fibonacci dp[i]=dp[i-1]+dp[i-2]; Decode Ways counts decodings with zero edge cases. O(n) time, O(1) space with rolling.

◷ 28 min

You now know the two ways to run a DP: memoization top-down and tabulation bottom-up. But both of those are just engines. The real skill is reading a brand-new problem and seeing the DP hiding inside it: what is the state, and how does one answer build on the answers before it? This lesson drills the most common shape of all—one-dimensional DP, where the state is a single position i in a sequence and dp[i] is decided by just a couple of earlier cells. Three classic problems, all the same skeleton: House Robber, Climbing Stairs, and Decode Ways. Learn to spot this shape and a huge slice of “hard” interview problems collapses into a one-line recurrence and a loop.

Goal

After this lesson you can recognize and solve one-dimensional dynamic programming problems. You can carry out the four-step routine for any of them: (1) define the state—what does dp[i] mean in one precise sentence; (2) write the recurrence that relates dp[i] to a few earlier cells; (3) set the base cases; (4) name the answer cell. You can apply it to three classics: House Robber (dp[i] = max(dp[i-1], dp[i-2] + nums[i]), never rob adjacent houses), Climbing Stairs (dp[i] = dp[i-1] + dp[i-2]—it is Fibonacci), and Decode Ways (count decodings of a digit string, handling the '0' edge cases). You can shrink each from an O(n) array to O(1) space using rolling variables, because the recurrence only looks back a fixed distance. Next lesson moves to two-dimensional DP, where the state is a pair (i, j).

The idea

What “one-dimensional DP” means

A one-dimensional DP is a dynamic program whose state is a single index i—usually a position in an array or string. You build an array dp where dp[i] is the answer to the subproblem ending at (or using) position i, and the recurrence expresses dp[i] using only a fixed number of earlier cells (almost always dp[i-1] and dp[i-2]). That “looks back only a constant distance” property is exactly what later lets you drop the whole array and keep just a few variables.

The four-step routine

Every problem below is solved with the same checklist. Memorize the questions, not the answers:

State. Finish this sentence precisely: “dp[i] is …”. A vague state is the #1 cause of wrong DPs.
Recurrence. How is dp[i] built from earlier cells? This is the one creative line.
Base cases. The smallest inputs the recurrence cannot reach (dp[0], sometimes dp[1]).
Answer cell. Which entry holds the final result—usually dp[n-1] or dp[n].

Problem 1 — House Robber

You are a burglar on a street of houses, nums[i] cash in house i. Robbing two adjacent houses trips the alarm. Maximize the loot.

State: dp[i] = the most you can rob considering houses 0..i.
Recurrence: at house i you either skip it (keep dp[i-1]) or rob it (take nums[i] plus the best from two back, dp[i-2], because i-1 is now off-limits): dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Base cases: dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]).
Answer: dp[n-1].

Watch the table fill for nums = [2, 7, 9, 3, 1]. Each cell is the better of “skip” (the cell to its left) and “rob” (cell two to the left plus this house):

index     i=0   i=1   i=2    i=3    i=4
nums       2     7     9      3      1
                |     |      |      |
skip  dp[i-1]:  -     2      7     11     11
rob   dp[i-2]+n:-    (-+7)  (2+9) (7+3) (11+1)
                            = 11  = 10   = 12
                |     |      |      |
dp:        2     7    11     11     12   <- answer = 12

The greedy “always grab the richest house” would fail; DP weighs every skip-vs-rob choice using the answers it already computed.

Problem 2 — Climbing Stairs (it is Fibonacci)

You climb a staircase of n steps, taking 1 or 2 steps at a time. How many distinct ways to reach the top?

State: dp[i] = the number of distinct ways to reach step i.
Recurrence: the last move landed on step i either from step i-1 (a 1-step) or from step i-2 (a 2-step), so dp[i] = dp[i-1] + dp[i-2]. That is the Fibonacci rule.
Base cases: dp[0] = 1 (one way to “stand at the bottom”—do nothing); dp[1] = 1 (a single 1-step).
Answer: dp[n].

step i:   0   1   2   3   4   5
ways:     1   1   2   3   5   8   <- climb(5) = 8
                  ^   ^
            2=1+1   3=2+1  (each = sum of the two before it)

Problem 3 — Decode Ways

A=1, B=2, ..., Z=26. Given a digit string like "226", count how many ways it decodes ("226" → "BBF", "BZ", "VF" = 3). The twist is the zeros and the 1–26 range.

State: dp[i] = the number of ways to decode the first i characters of the string. (Note the off-by-one: dp is indexed by length processed, not by character position, so dp has n+1 cells.)
Recurrence: look at the last one or two characters before length i.
- If the single digit s[i-1] is '1'–'9' (not '0'), it forms a valid letter on its own → add dp[i-1].
- If the two digits s[i-2..i-1] form a number 10–26, they form a valid letter together → add dp[i-2].
- dp[i] = (s[i-1] != '0' ? dp[i-1] : 0) + (10 <= twoDigit <= 26 ? dp[i-2] : 0).
Base cases: dp[0] = 1 (one way to decode the empty prefix); dp[1] = 1 if s[0] is not '0', else 0 (a leading zero decodes nothing).
Answer: dp[n].

The zero is what makes this hard. '0' is never a letter by itself (there is no letter 0), so a lone '0' contributes nothing, and only "10" and "20" ever consume a '0' validly (as J and T). Anything like "30", "06", or a trailing "...0" with no valid two-digit partner means zero total decodings—the whole count collapses to 0.

"226":  dp[0]=1  dp[1]=1  dp[2]=2  dp[3]=3
"06" :  s[0]='0' -> dp[1]=0 -> answer 0   (leading zero, dead)
"100":  ...the final '0' has no valid 2-digit partner ("00") -> 0

The code

House Robber, the textbook 1D DP

Here is House Robber with an explicit dp array so the recurrence is visible, then we collapse it.


      1
      function rob(nums) {
    

      2
      const n = nums.length;
    

      3
      if (n === 0) return 0;
    

      4
      if (n === 1) return nums[0];
    

      5
       
    

      6
      const dp = new Array(n);
    

      7
      dp[0] = nums[0];                       // base: only house 0
    

      8
      dp[1] = Math.max(nums[0], nums[1]);    // base: best of the first two
    

      9
       
    

      10
      for (let i = 2; i < n; i++) {
    

      11
        // skip house i  -> dp[i-1]
    

      12
        // rob  house i  -> dp[i-2] + nums[i]  (i-1 is now forbidden)
    

      13
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    

      14
      }
    

      15
       
    

      16
      return dp[n - 1];                      // answer cell
    

      17
      }

L3 Edge case: no houses means no loot.
L4 Edge case: a single house is robbed outright.
L7 Base case dp[0]: the only option is to rob house 0.
L8 Base case dp[1]: rob whichever of the first two houses holds more.
L13 The recurrence: best of skipping house i (dp[i-1]) versus robbing it (dp[i-2] + nums[i]).
L16 The answer is the last cell: best loot over all houses.

Collapsing to O(1) space

dp[i] only ever reads dp[i-1] and dp[i-2]. So we never need the whole array—two rolling variables suffice. This same trick works for all three problems because each recurrence looks back a fixed distance.

prev2 = dp[i-2]   prev1 = dp[i-1]
cur = recurrence(prev1, prev2)
then slide: prev2 = prev1, prev1 = cur

Running all three (rolling, O(1) space)

// House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
function rob(nums) {
let prev2 = 0;            // best up to i-2
let prev1 = 0;            // best up to i-1
for (const x of nums) {
  const take = prev2 + x; // rob this house
  const skip = prev1;     // skip this house
  const cur = Math.max(skip, take);
  prev2 = prev1;
  prev1 = cur;
}
return prev1;
}

// Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]  (Fibonacci)
function climbStairs(n) {
let prev2 = 1;            // ways to reach step 0
let prev1 = 1;            // ways to reach step 1
for (let i = 2; i <= n; i++) {
  const cur = prev1 + prev2;
  prev2 = prev1;
  prev1 = cur;
}
return prev1;
}

// Decode Ways: 1-digit and valid 2-digit predecessors, zeros are deadly
function numDecodings(s) {
if (s.length === 0 || s[0] === "0") return 0;
let prev2 = 1;            // dp[0]: empty prefix
let prev1 = 1;            // dp[1]: first char is non-zero here
for (let i = 2; i <= s.length; i++) {
  let cur = 0;
  if (s[i - 1] !== "0") cur += prev1;          // single digit 1..9
  const two = Number(s.slice(i - 2, i));       // last two digits
  if (two >= 10 && two <= 26) cur += prev2;    // valid pair 10..26
  prev2 = prev1;
  prev1 = cur;
}
return prev1;
}

console.log("House Robber:");
console.log("  [2,7,9,3,1] ->", rob([2, 7, 9, 3, 1]));
console.log("  [1,2,3,1]   ->", rob([1, 2, 3, 1]));
console.log("Climbing Stairs:");
console.log("  n=5  ->", climbStairs(5));
console.log("  n=10 ->", climbStairs(10));
console.log("Decode Ways:");
console.log("  '226' ->", numDecodings("226"));
console.log("  '06'  ->", numDecodings("06"));
console.log("  '100' ->", numDecodings("100"));

Output

The '06' returns 0 (leading zero) and '100' returns 0 (the final '0' has no valid two-digit partner)—the zero edge cases the recurrence must respect.

Step-by-step trace

Let us fill the House Robber table for nums = [2, 7, 9, 3, 1] cell by cell. Each dp[i] is the better of skip (dp[i-1]) and rob (dp[i-2] + nums[i]).


      1
      dp[0] = nums[0];
    

      2
      dp[1] = max(nums[0], nums[1]);
    

      3
      for (let i = 2; i < n; i++)
    

      4
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    

      5
      return dp[n-1];

Complexity

Time: O(n)

All three problems do one pass over an input of length n, and each cell costs O(1) work (a max, or one or two additions, or a couple of digit checks). So time is the number of states times the per-state work: n states x O(1) = O(n).

problem           states   work/state   time
House Robber      n        O(1)         O(n)
Climbing Stairs   n+1      O(1)         O(n)
Decode Ways       n+1      O(1)         O(n)

Space: O(n) with an array, O(1) with rolling variables

The naive table stores every dp[i]: O(n) space. But every recurrence here reads back only a fixed distance—dp[i-1] and dp[i-2]—so you only ever need the last two values. Replace the array with two variables (prev1, prev2) and slide them forward each step:

                  array      rolling
House Robber      O(n)       O(1)
Climbing Stairs   O(n)       O(1)
Decode Ways       O(n)       O(1)

The rule that licenses O(1) space: if dp[i] depends only on the last k cells, you need only k variables, not the whole array. Here k = 2 for all three. This is the signature optimization of one-dimensional DP, and it is why interviewers love these problems—they want to see you spot the bounded look-back and drop the array.

(Caveat: if a later question asks you to reconstruct the actual choices—which houses were robbed, which decoding was used—you must keep the full array or parent pointers. Rolling variables give you the count or the optimum value, but they throw away the path.)

Practice 0 / 8

What is the House Robber recurrence (cannot rob two adjacent houses)?

Why is Climbing Stairs the same as Fibonacci?

In Decode Ways, what does the state dp[i] represent?

How many ways can the string '226' be decoded (A=1..Z=26)?

Why does the string '06' decode in 0 ways?

Why can House Robber, Climbing Stairs, and Decode Ways all run in O(1) space?

For House Robber with nums = [2, 7, 9, 3, 1], what is the maximum loot (the answer cell dp[4])?

Climbing Stairs with n = 5: how many distinct ways to reach the top (1 or 2 steps at a time)?

Why this works

Why “define the state in one precise sentence” matters so much. Most wrong DPs are not wrong recurrences—they are vague states. “dp[i] is the answer so far” means nothing you can write a recurrence against. Compare the three crisp definitions here: House Robber’s dp[i] is “the most you can rob considering houses 0..i”; Decode Ways’ dp[i] is “the number of ways to decode the first i characters.” Once the sentence is exact, the recurrence usually writes itself, because you can ask “given that definition, how does cell i depend on earlier cells?” and the answer is forced. Spend your thinking time on the state, not the code.

Edge cases

The zeros in Decode Ways. This is the edge case that breaks naive solutions. Three things to get right: (1) A leading ‘0’ (s[0] === '0') means the whole string decodes 0 ways—bail out immediately. (2) A lone ‘0’ is never a letter, so the single-digit branch must check s[i-1] !== '0' before adding dp[i-1]. (3) A ‘0’ is only valid as the second digit of “10” or “20”; “30”..“90” and “00” are invalid pairs, so a ‘0’ with no valid partner (like the trailing ‘0’ in “100”, or “06”, or “30”) forces dp[i]=0 and the count dies. Test your code on “10” (=1, valid as J), “100” (=0), “2101” (=1), and “06” (=0).

Common mistake

Forgetting that Decode Ways is indexed by length, not position. It is tempting to make dp[i] mean “decodings ending exactly at character i,” but the clean version indexes dp by the number of characters consumed: dp[i] = ways to decode the first i characters. That gives dp.length = n+1, the empty-prefix base case dp[0]=1, and the answer dp[n]. Mixing the two conventions is a classic off-by-one that produces correct-looking-but-wrong counts. Pick the length convention and the base cases line up cleanly.

More practice

The four-step routine on a fresh problem. Try “Min Cost Climbing Stairs”: each step i has a cost[i]; you may start at step 0 or 1, climb 1 or 2 at a time, pay the cost of each step you stand on, and reach past the top. (1) State: dp[i] = minimum cost to reach step i. (2) Recurrence: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). (3) Base: dp[0] = cost[0], dp[1] = cost[1]. (4) Answer: min(dp[n-1], dp[n-2]) (you can step past the top from either of the last two). Same skeleton, new recurrence — that is the whole pattern. Then collapse it to O(1) space with two rolling variables.

Check yourself

Quiz

Explain the one-dimensional DP pattern: what the state is, how the three problems' recurrences work, the Decode Ways zero edge cases, and why O(1) space is possible.

Recap

One-dimensional DP has a single-index state: dp[i] answers the subproblem at position i, and the recurrence reads only a fixed number of earlier cells. Solve any of them with four steps: define the state precisely, write the recurrence, set the base cases, name the answer cell.

The three classics:

House Robber — dp[i] = max(dp[i-1], dp[i-2] + nums[i]); skip vs rob, never two adjacent. Answer dp[n-1].
Climbing Stairs — dp[i] = dp[i-1] + dp[i-2]; it is Fibonacci, counting ways by the last (1- or 2-) step. Answer dp[n].
Decode Ways — dp[i] = ways to decode the first i characters; add dp[i-1] when the single digit is non-zero and dp[i-2] when the last two digits are 10–26. A leading '0' or an unpaired '0' (like '06', '100', '30') drops the count to 0.

Complexity: O(n) time for all three. O(1) space with rolling variables, because each recurrence looks back only two cells—the signature optimization of 1D DP. (Keep the full array only if you must reconstruct the actual choices.)

Next: two-dimensional DP, where the state becomes a pair (i, j)—grids, edit distance, and subsequence problems—but the same four-step routine still drives every one.

Continue the climb ↑Two-dimensional DP: grid paths, LCS, edit distance