Climbing Staircase

You are climbing a staircase that requires $n$ steps to reach the top. Each time, you can climb either 1 or 2 steps. Determine the number of distinct ways to reach the top.

Examples

Example 1:

• Input: $n=2$
• Output: 2
• Ways: (1+1), (2)

Example 2:

• Input: $n=3$
• Output: 3
• Ways: (1+1+1), (1+2), (2+1)

Strategy

This problem follows the Fibonacci sequence pattern. To reach step $n$, you must have come from either step $n-1$ (taking 1 step) or step $n-2$ (taking 2 steps):

$ways(n)=ways(n-1)+ways(n-2)$

A naive recursive solution has exponential time complexity $O(2^n)$. The solution employs memoization using a hash map to store computed values, similar to the optimization techniques used in House Robber. This reduces time complexity to $O(n)$ with $O(n)$ space.

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];
  }
};