Leetcode - Climbing Stairs

Leetcode : Climbing Stairs

Description

You are climbing a stair case. It takes n steps to reach to 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

2

Output

2
// There are two ways to climb to the top.
// 1. 1 step + 1 step
// 2. 2 steps

Example 2

Input

3

Output

3
// There are three ways to climb to the top.
// 1. 1 step + 1 step + 1 step
// 2. 2 steps + 1 step
// 3. 1 step + 2 steps

Approach

Break the steps in sub-problems in a recursive manner - Dynamic Programming (i.e - answer[N] = answer[N-1] + answer[N-2])

Solutions

Solution I (C++)

class Solution {
public:
    int climbStairs(int n) {
        unordered_map<int, int> dp;
        
        if (n <= 1)
            return 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];
        
    }
};

Solution II (C++)

class Solution {
public:
    int climbStairs(int n) {
        unsigned int a = 1, b = 1;
        while(n--)
        {
           a = (b = a + b) - a; 
        }
        
        return a;
    }
};