Day 5 Leet code series, today we will be picking the problem Climbing Stairs (https://leetcode.com/problems/climbing-stairs/).

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

Solution 1: Without memoization and recursion(will give timeout error after 44)

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

Solution 2: With arrays only (will pass all cases):

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

Solution 3: With recursion and memoization.

class Solution {
public:
    int climbStairs(int n) {
        unordered_map<int, int> map;
        return helper(0, n, map);
    }
    
    int helper(int i, int n, unordered_map<int, int> &map){
        if(i>n) return 0;
        else if(i == n) return 1;
        else{
            if(map.find(i) != map.end()){
                return map[i];
            }
            else{
                int val = helper(i+1, n, map) + helper(i+2, n, map);
                map[i] = val;
                return val;
            }
        }
    }
};