Climbing Staircase

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

Strategy

Step n can be reached from two steps before it, n-1 and n-2. So ways to reach n can be written as:

$$\begin{gathered} ways(n)=ways(n-1)+ways(n-2) \\ ways(n)=2\ast ways(n-2)+ways(n-3) \end{gathered}$$

So the function can be recurssively called for n-1 and n-2. But this has a very high time complexity, hence, the calculated values need to be stored in a hash map to avoid calculating them multiple times.

Solution

#include <unordered_map>
using namespace std;
 
class Solution {
public:
  unordered_map<int, int> createHash() {
    unordered_map<int, int> hashMap;
    hashMap[1] = 1;
    hashMap[2] = 2;
    return hashMap;
  }
  unordered_map<int, int> hashMap = createHash();
  int climbStairs(int n) {
    if (hashMap.count(n))
      return hashMap[n];
    hashMap[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return hashMap[n];
  }
};