Climbing Stairs

Problem

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

Solution

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = Array(n).fill(null);
    dp[0] = 1;
    dp[1] = 2;

    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n - 1];
};

We will implement a DP solution. Let dp[i] be the number of unique ways to climb i + 1 steps.

For the base case, if i = 0 or i = 1, then there are 1 and 2 distinct ways to climb respectively.
For the recursive case, since we can climb either one or two steps at once, the total number of distinct ways can be computed with dp[i - 1] + dp[i - 2] (ie. all the ways in dp[i - 1] plus one step reaches the top, and all the ways in dp[i - 2] plus two steps reaches the top).

Problem​

Solution​

Problem

Solution