#50 · 1D DP

Climbing Stairs

You climb a staircase of n steps, taking 1 or 2 steps at a time. In how many distinct ways can you reach the top?

EasyLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

One-dimensional DP table

dp[i] stores the answer to the smaller problem "ways to reach stair i". Each entry depends only on the previous two, so the whole table can be computed left to right.

Memory layout

A flat array of n + 1 integers. Because only two earlier entries are read, two variables are enough.

Operation	Cost
time	O(n)
space	O(n) table, O(1) with two variables

Fibonacci recurrence

The last step is either a 1-step from stair i − 1 or a 2-step from stair i − 2, so ways(i) = ways(i − 1) + ways(i − 2). With ways(0) = ways(1) = 1 these are the Fibonacci numbers.

Memory layout

Pairs of consecutive values; matrix or doubling identities jump k → 2k.

Operation	Cost
nth term	O(log n) with fast doubling

Why it fits

The problem has optimal substructure: the ways to reach stair i are built entirely from the ways to reach two smaller stairs.
The same sub-answers are needed again and again (ways(3) is used by both ways(4) and ways(5)), so storing them turns an exponential recursion into a linear loop.
Since each value needs only the previous two, you can drop the table, or even skip ahead with doubling identities.

Why alternatives degrade

Plain recursion:: It recomputes the same values exponentially often: the number of calls grows like 1.6^n.
Enumerating all paths:: The number of paths is the answer itself, which grows exponentially; listing them is hopeless, counting them is easy.
Greedy:: There is nothing to optimise: every valid route counts, so no local choice can be ruled out.

Four approaches, from naive to production

1 · beginner

Plain recursion

time O(2ⁿ)space O(n) recursion

To reach the top from stair s you took either 1 or 2 steps, so ways(s) = ways(s − 1) + ways(s − 2). Stop at 0 (one way) and below 0 (no way).

int climbStairs(int n) {
    function<int(int)> ways = [&](int step) -> int {
        if (step == 0) return 1;
        if (step < 0) return 0;
        return ways(step - 1) + ways(step - 2);
    };
    return ways(n);
}

public int climbStairs(int n) {
    return ways(n);
}
private int ways(int step) {
    if (step == 0) return 1;
    if (step < 0) return 0;
    return ways(step - 1) + ways(step - 2);
}

def climb_stairs(n):
    def ways(step):
        if step == 0: return 1
        if step < 0: return 0
        return ways(step - 1) + ways(step - 2)
    return ways(n)

function climbStairs(n: number): number {
  const ways = (step: number): number => {
    if (step === 0) return 1;
    if (step < 0) return 0;
    return ways(step - 1) + ways(step - 2);
  };
  return ways(n);
}

Flaws & bottlenecks

The same stairs are solved over and over: ways(3) is recomputed inside both ways(4) and ways(5).
The number of calls roughly doubles with every extra stair.
Recursion depth is n, which may overflow the stack for large n.

Interviewer cross-questions

Why is it exponential?

Say: Each call makes two further calls and the recursion tree has depth n, so the number of calls is about the Fibonacci number itself: roughly 1.6ⁿ.

How do you spot overlapping subproblems?

Say: Draw the call tree for a small n: identical sub-trees (like ways(3)) appear many times. That repetition is the signal to cache or tabulate.

What are the base cases?

Say: ways(0) = 1 (one way to stay put) and ways(negative) = 0. Together they make ways(1) = 1 and ways(2) = 2.

2 · intermediate

Memoised recursion

time O(n)space O(n)

Keep the recursion but store each result in a table keyed by the stair. If the answer is already stored, return it at once. Each stair is solved only once.

int climbStairs(int n) {
    unordered_map<int, int> memo;
    function<int(int)> ways = [&](int step) -> int {
        if (step <= 1) return 1;
        auto known = memo.find(step);
        if (known != memo.end()) return known->second;
        int result = ways(step - 1) + ways(step - 2);
        memo[step] = result;
        return result;
    };
    return ways(n);
}

public int climbStairs(int n) {
    Map<Integer, Integer> memo = new HashMap<>();
    return ways(n, memo);
}
private int ways(int step, Map<Integer, Integer> memo) {
    if (step <= 1) return 1;
    Integer known = memo.get(step);
    if (known != null) return known;
    int result = ways(step - 1, memo) + ways(step - 2, memo);
    memo.put(step, result);
    return result;
}

def climb_stairs(n):
    memo = {}
    def ways(step):
        if step <= 1: return 1
        known = memo.get(step)
        if known is not None: return known
        result = ways(step - 1) + ways(step - 2)
        memo[step] = result
        return result
    return ways(n)

function climbStairs(n: number): number {
  const memo = new Map<number, number>();
  const ways = (step: number): number => {
    if (step <= 1) return 1;
    const known = memo.get(step);
    if (known !== undefined) return known;
    const result = ways(step - 1) + ways(step - 2);
    memo.set(step, result);
    return result;
  };
  return ways(n);
}

Flaws & bottlenecks

Still recursive: depth n can overflow the stack for large n.
Hash-table overhead for what is really a dense range of integers.
The call overhead makes it slower than a simple loop.

Interviewer cross-questions

What exactly does memoisation change?

Say: Each distinct stair is computed once and every later request is a lookup, so the total work drops from exponential to linear.

Top-down or bottom-up?

Say: Both are O(n). Top-down is easy to write straight from the recurrence; bottom-up avoids recursion and function-call cost.

Why is step <= 1 a single base case?

Say: ways(0) and ways(1) are both 1, so one test covers both and keeps the recursion from reaching negative steps.

3 · advanced

Bottom-up table

time O(n)space O(n)

Fill an array from the bottom: dp[0] = dp[1] = 1, then dp[i] = dp[i − 1] + dp[i − 2] for each higher stair. The answer is dp[n].

int climbStairs(int n) {
    if (n <= 1) return 1;
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

public int climbStairs(int n) {
    if (n <= 1) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

def climb_stairs(n):
    if n <= 1: return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

function climbStairs(n: number): number {
  if (n <= 1) return 1;
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

Flaws & bottlenecks

Uses O(n) memory for values that are needed only briefly.
Overflow: the answer grows like 1.6ⁿ, so 32-bit integers overflow around n = 45 (the problem limits n to 45).
Needs the n ≤ 1 guard because dp[1] would not exist for n = 0.

Interviewer cross-questions

Why is order important?

Say: dp[i] needs dp[i − 1] and dp[i − 2] to be final. Iterating upward guarantees they are.

How much memory is really needed?

Say: Only the last two values: two variables replace the whole table and bring the space to O(1).

What if n is huge?

Say: The numbers explode past 64 bits quickly. You would need big integers or the answer modulo a given number, and possibly the O(log n) doubling method.

4 · expert

Fast doubling over the bits of n + 1

time O(log n) arithmetic stepsspace O(1)

Because ways(n) = F(n + 1), keep a pair (F(k), F(k + 1)) and double k with two identities, adding one more bit of n + 1 at a time. This computes the answer in about log₂ n steps.

int climbStairs(int n) {
    long long a = 0, b = 1;
    for (int bit = 31 - __builtin_clz(n + 1); bit >= 0; bit--) {
        long long c = a * (2 * b - a);
        long long d = a * a + b * b;
        if (((n + 1) >> bit) & 1) {
            a = d;
            b = c + d;
        } else {
            a = c;
            b = d;
        }
    }
    return (int)a;
}

public int climbStairs(int n) {
    long a = 0, b = 1;
    for (int bit = 31 - Integer.numberOfLeadingZeros(n + 1); bit >= 0; bit--) {
        long c = a * (2 * b - a);
        long d = a * a + b * b;
        if ((((n + 1) >> bit) & 1) == 1) {
            a = d;
            b = c + d;
        } else {
            a = c;
            b = d;
        }
    }
    return (int) a;
}

def climb_stairs(n):
    a, b = 0, 1
    for bit in range((n + 1).bit_length() - 1, -1, -1):
        c = a * (2 * b - a)
        d = a * a + b * b
        if ((n + 1) >> bit) & 1:
            a = d
            b = c + d
        else:
            a = c
            b = d
    return a

function climbStairs(n: number): number {
  let a = 0, b = 1;
  for (let bit = 31 - Math.clz32(n + 1); bit >= 0; bit--) {
    const c = a * (2 * b - a);
    const d = a * a + b * b;
    if (((n + 1) >> bit) & 1) {
      a = d;
      b = c + d;
    } else {
      a = c;
      b = d;
    }
  }
  return a;
}

Flaws & bottlenecks

Much harder to read and verify than the linear loop, and for n ≤ 45 the gain is negligible.
The intermediate products overflow 32-bit integers sooner than the plain loop would for large n (use 64-bit or big integers).
Relies on the link ways(n) = F(n + 1); it is easy to be off by one.

Interviewer cross-questions

Where do the doubling formulas come from?

Say: They are the matrix identity [[1,1],[1,0]]^(2k) = ([[1,1],[1,0]]^k)², multiplied out: F(2k) = F(k)(2F(k+1) − F(k)) and F(2k+1) = F(k)² + F(k+1)².

Why go through the bits of n + 1?

Say: Building k from the top bit down, each step either doubles k or doubles it and adds 1, so after one pass k equals n + 1 exactly.

When would you use this in production?

Say: For computing very large Fibonacci-type values (with modular arithmetic or big integers) where a linear loop would be too slow. For small n, the simple loop is clearer and fast enough.

Synchronized code walkthrough

Showing: Plain recursion — shares the player above; click any step to jump.

int climbStairs(int n) {
    function<int(int)> ways = [&](int step) -> int {
        if (step == 0) return 1;
        if (step < 0) return 0;
        return ways(step - 1) + ways(step - 2);
    };
    return ways(n);
}

public int climbStairs(int n) {
    return ways(n);
}
private int ways(int step) {
    if (step == 0) return 1;
    if (step < 0) return 0;
    return ways(step - 1) + ways(step - 2);
}

def climb_stairs(n):
    def ways(step):
        if step == 0: return 1
        if step < 0: return 0
        return ways(step - 1) + ways(step - 2)
    return ways(n)

function climbStairs(n: number): number {
  const ways = (step: number): number => {
    if (step === 0) return 1;
    if (step < 0) return 0;
    return ways(step - 1) + ways(step - 2);
  };
  return ways(n);
}

int climbStairs(int n) {
    unordered_map<int, int> memo;
    function<int(int)> ways = [&](int step) -> int {
        if (step <= 1) return 1;
        auto known = memo.find(step);
        if (known != memo.end()) return known->second;
        int result = ways(step - 1) + ways(step - 2);
        memo[step] = result;
        return result;
    };
    return ways(n);
}

public int climbStairs(int n) {
    Map<Integer, Integer> memo = new HashMap<>();
    return ways(n, memo);
}
private int ways(int step, Map<Integer, Integer> memo) {
    if (step <= 1) return 1;
    Integer known = memo.get(step);
    if (known != null) return known;
    int result = ways(step - 1, memo) + ways(step - 2, memo);
    memo.put(step, result);
    return result;
}

def climb_stairs(n):
    memo = {}
    def ways(step):
        if step <= 1: return 1
        known = memo.get(step)
        if known is not None: return known
        result = ways(step - 1) + ways(step - 2)
        memo[step] = result
        return result
    return ways(n)

function climbStairs(n: number): number {
  const memo = new Map<number, number>();
  const ways = (step: number): number => {
    if (step <= 1) return 1;
    const known = memo.get(step);
    if (known !== undefined) return known;
    const result = ways(step - 1) + ways(step - 2);
    memo.set(step, result);
    return result;
  };
  return ways(n);
}

int climbStairs(int n) {
    if (n <= 1) return 1;
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

public int climbStairs(int n) {
    if (n <= 1) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

def climb_stairs(n):
    if n <= 1: return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

function climbStairs(n: number): number {
  if (n <= 1) return 1;
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

int climbStairs(int n) {
    long long a = 0, b = 1;
    for (int bit = 31 - __builtin_clz(n + 1); bit >= 0; bit--) {
        long long c = a * (2 * b - a);
        long long d = a * a + b * b;
        if (((n + 1) >> bit) & 1) {
            a = d;
            b = c + d;
        } else {
            a = c;
            b = d;
        }
    }
    return (int)a;
}

public int climbStairs(int n) {
    long a = 0, b = 1;
    for (int bit = 31 - Integer.numberOfLeadingZeros(n + 1); bit >= 0; bit--) {
        long c = a * (2 * b - a);
        long d = a * a + b * b;
        if ((((n + 1) >> bit) & 1) == 1) {
            a = d;
            b = c + d;
        } else {
            a = c;
            b = d;
        }
    }
    return (int) a;
}

def climb_stairs(n):
    a, b = 0, 1
    for bit in range((n + 1).bit_length() - 1, -1, -1):
        c = a * (2 * b - a)
        d = a * a + b * b
        if ((n + 1) >> bit) & 1:
            a = d
            b = c + d
        else:
            a = c
            b = d
    return a

function climbStairs(n: number): number {
  let a = 0, b = 1;
  for (let bit = 31 - Math.clz32(n + 1); bit >= 0; bit--) {
    const c = a * (2 * b - a);
    const d = a * a + b * b;
    if (((n + 1) >> bit) & 1) {
      a = d;
      b = c + d;
    } else {
      a = c;
      b = d;
    }
  }
  return a;
}