Climbing Stairs

easy dp fibonacci

Problem

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps.

Inputn = 5

Output8

Recurrence: dp[i] = dp[i−1] + dp[i−2].

n (steps)

def climb_stairs(n):
    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) {
  const dp = new Array(n + 1);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

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

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

Explanation

Think about the last move you make to reach step n. It was either a single step (from step n−1) or a double step (from step n−2). There is no other way to arrive.

So the number of ways to reach step n is simply the ways to reach n−1 plus the ways to reach n−2. That is the same rule as the Fibonacci sequence.

We build the answer from the bottom up. There is 1 way to stand at the start and 1 way to reach the first step. From there, each step's count is the sum of the two before it.

We store these counts in an array dp so each value is computed once and reused, instead of recalculating the same thing over and over.

Example: for n = 5 the counts go 1, 1, 2, 3, 5, 8 — so there are 8 ways to climb.

Time: O(n) Space: O(n) (can be reduced to O(1))