1D Dynamic Programming

The problem

You are standing at the bottom of a staircase with n steps. You can hop up one step or two steps at a time. How many different ways can you reach the top? For 3 steps you can list them: 1+1+1, 1+2, 2+1 — three ways. For 5 steps you can still enumerate them if you are patient. For 45 steps there are over a billion, and listing them by hand is hopeless.

This looks like a counting puzzle, but underneath it is the same machine as robbing houses on a street, or making change for a total, or the maximum sum you can grab without picking two neighbors. All of them fill a single array, left to right, each cell depending on a few cells just behind it.

A first attempt

The recursive definition writes itself: to reach step n, your last hop came from step n-1 or step n-2. So the number of ways is the sum of the ways to reach each of those.

def climb(n):
    if n <= 2:
        return n
    return climb(n - 1) + climb(n - 2)

That is Fibonacci in disguise, and it has Fibonacci's disease: the same climb(k) is recomputed exponentially many times, giving O(φⁿ) time. climb(45) will keep your CPU busy for an uncomfortably long while.

The insight

Every 1D DP shares one shape:

The answer for position i depends on a constant number of earlier positions. Store those answers in an array, fill it once from left to right, and each cell costs O(1).

The only thing that changes from problem to problem is the recurrence:

• Climbing stairs: dp[i] = dp[i-1] + dp[i-2] (count of ways).
• House robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (skip this house or take it).
• Coin change: dp[a] = min(dp[a - c] + 1) over every coin c (fewest coins for amount a).

Learn to spot "one dimension, a few steps back" and half the DP problems you meet become the same problem.

How it works

Take House Robber: houses in a row each hold some cash, and you cannot rob two adjacent houses or the alarm trips. Maximize the take.

The code

def rob(nums):
    prev2, prev1 = 0, 0  # dp[i-2], dp[i-1]
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

function rob(nums: number[]): number {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

class Solution {
    int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

int rob(int *nums, int n) {
    int prev2 = 0, prev1 = 0;
    for (int i = 0; i < n; i++) {
        int cur = prev1 > prev2 + nums[i] ? prev1 : prev2 + nums[i];
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int rob(vector<int> &nums) {
    int prev2 = 0, prev1 = 0;
    for (int x : nums) {
        int cur = max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Complexity

Coin change is slightly bigger: dp[a] = min over coins makes it O(amount × coins) time and O(amount) space, since each amount looks back once per coin.

When to use it

Practice

Recap

• A 1D DP fills a single array where each cell depends on a fixed number of earlier cells.
• The skeleton is identical across problems; only the recurrence and combine operator (sum vs max vs min) change.
• When the look-back distance is constant, collapse the array into rolling variables for O(1) space.