LeetCode 70 · Easy · 1-D Dynamic Programming

Climbing Stairs

You climb a staircase of n steps, taking 1 or 2 steps at a time. Return how many distinct ways there are to reach the top.

O(n)time
O(1)space
Fibonaccirecurrence

n: whole number, 1 to 20 · the answer grows like Fibonacci (n = 20 already has 10946 ways) · LeetCode allows n ≤ 45

ways dp table · the code only keeps the cells under one and two

public int climbStairs(int n) { int one = 1; // ways[1] int two = 1; // ways[0] for (int i = 2; i <= n; i++) { int temp = one; one = one + two; // ways[i] two = temp; } return one;}
n
—
i
—
one
—
two
—
temp
—

Why it works

  1. Brute force recurses: climb(n) = climb(n−1) + climb(n−2). Each call spawns two more, so the call tree has about 1.6ⁿ leaves, O(2ⁿ). climb(n−2) is solved again inside climb(n−1), and so on down.
  2. The last move decides: you reach step i by a +1 from i−1 or a +2 from i−2. Those two groups never overlap, so ways[i] = ways[i−1] + ways[i−2], with ways[0] = ways[1] = 1. That is Fibonacci, shifted by one.
  3. Memoise, then go bottom-up. Caching each climb(i) makes it O(n) time and O(n) space. Filling the table from 0 upward does the same without recursion.
  4. Only two cells are ever read, so two variables replace the table: O(1) space. Watch the order: one = one + two; two = one would copy the new value. Save the old one in temp, or compute int next = one + two; first, then two = one; one = next;.
  5. It grows fast: about ×1.6 per step. LeetCode stops at n = 45 (1,836,311,903 ways) so the answer fits an int.
  6. Follow-ups: Min Cost Climbing Stairs uses the same two-cell window with min. Moves of {1, 2, 3} add a third term. For huge n, matrix power gives O(log n). House Robber, next, adds a choice at each step.