1D DP

Climbing Stairs

To reach step i, you came from step i-1 (one step) or i-2 (two steps). So dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[0]=1, dp[1]=1. This is literally the Fibonacci sequence! You only need two variables.

O(n)

O(1)

say this out loud

Each step depends on the previous two, so it is Fibonacci in disguise. Two variables are enough, so O(n) time and O(1) space.

How It Works

Climbing Stairs is the canonical introduction to 1D DP. To stand on step i you must have arrived from step i-1 (a single step) or step i-2 (a double step), so the number of ways satisfies dp[i] = dp[i-1] + dp[i-2] with base cases dp[0] = 1 and dp[1] = 1. This recurrence is exactly the Fibonacci sequence, and it collapses an exponential tree of choices into n additions because every distinct subproblem is solved once and reused.

Since each state only reads the two previous values, the full array is unnecessary: two rolling variables give O(n) time and O(1) space. The same counting-paths-backward reasoning powers many step, tiling, and decoding problems.

Step-by-Step Visualization

n = 5 stairs, 1 or 2 at a time. dp[i] = ways to reach step i

dp[0]1

dp[1]1

1/6

Code

Java

static int climbStairs(int n) {
  int prev2 = 1, prev1 = 1;
  for (int i = 2; i <= n; i++) {
    int curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
// climbStairs(5) → 8

Tips & Gotchas

1dp[i] = dp[i-1] + dp[i-2] (like Fibonacci)

2Only need previous two values, so O(1) space

3Base cases: dp[0]=1 (one way to stay), dp[1]=1

Practice Problems

1Climbing Stairs
2Fibonacci Number
3Min Cost Climbing Stairs
4N-th Tribonacci Number
5Decode Ways

About the 1D DP Pattern

The state is a single variable (usually an index). Each dp[i] depends on a few previous values like dp[i-1] or dp[i-2]. Often you can optimize space by keeping only the last 2-3 values instead of the whole array.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why does naive recursion for Climbing Stairs blow up?

The plain recursive solution recomputes the same subproblems exponentially many times, climb(n) calls climb(n-1) and climb(n-2), which overlap heavily. Memoization or bottom-up tabulation stores each answer once, cutting the work from O(2^n) to O(n).

How does this generalize when I can take up to k steps at a time?

The recurrence becomes dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k], a sum over the last k states. You can keep it O(n) overall by maintaining a sliding-window sum instead of re-adding k terms at every index.

Is Climbing Stairs a counting problem or an optimization problem?

It counts the number of distinct ways, so you add subproblem results rather than taking a max or min. Recognizing whether to sum or optimize is one of the first decisions in any DP formulation.