Climbing Stairs

Problem

You are given an integer n representing the number of steps to reach the top of a staircase. You can climb with either 1 or 2 steps at a time.

Return the number of distinct ways to climb to the top of the staircase.

Examples

Example 1:

Input: n = 2

Output: 2

Explanation:

1. 1 + 1 = 2
2. 2 = 2

Example 2:

Input: n = 3

Output: 3

1. 1 + 1 + 1 = 3
2. 1 + 2 = 3
3. 2 + 1 = 3

Constraints

• 1 <= n <= 45

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of steps.

Solution

DFS will consider all paths, and in this case it would duplicate a lot of work. Better to use DP (memorize the work done)

class Solution {
public:
    int climbStairs(int n) {
        // Base case
        if (n <= 2) { return n; }
        // The ways to get to stair i is the number of ways to get to 
        //   stair i-1 + stair i-2
        int prev_prev = 1;
        int prev = 2;
        for (int i = 3; i < n; ++i) {
            int curr = prev_prev + prev;
            prev_prev = prev;
            prev = curr;
        }
        return prev_prev + prev;
    }
};
 
// Non-optimized version
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};