70. Climbing Stairs

Problem

Tags: Math, Dynamic Programming, Memoization

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

Code

C

// 70. Climbing Stairs (2/18/54000)
// Runtime: 0 ms (93.70%) Memory: 5.72 MB (0.00%) 

int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }

    int64_t prev_1 = 2, prev_2 = 1, now = 0;

    for (int64_t i = 3; i <= n; i++) {
        now = prev_1 + prev_2;
        prev_2 = prev_1;
        prev_1 = now;
    }

    return now;
}

JS

// 70. Climbing Stairs (12/29/53742)
// Runtime: 78 ms (39.76%) Memory: 38.06 MB (92.87%) 

/**
 * @param {number} n
 * @return {number}
 */
function climbStairs(n) {
    const dp = [1, 2];
    for (let i = 2; i < n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n - 1];
}