# Climbing Stairs

Link: [https://leetcode.com/problems/climbing-stairs/](https://leetcode.com/problems/climbing-stairs/)

<details data-node-type="hn-details-summary"><summary>Problem Statement</summary><div data-type="detailsContent">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?</div></details>

> Recursive solution - Gives TLE

```cpp
class Solution {
public:
    int solve(int curr, int n){
        if (curr == n) return 1;
        if (curr > n) return 0;
        return solve(curr+1, n) + solve(curr+2, n);
    }
    
    int climbStairs(int n) {
        return solve(0, n);
    }
};
```

> Memoization solution - Accepted

```cpp
class Solution {
public:
    int solve(int curr, int n, unordered_map<int, int> &dp){
        if (curr == n) return 1;
        if (curr > n) return 0;
        if (dp.find(curr) != dp.end())  return dp[curr];
        dp[curr] = solve(curr+1, n, dp) + solve(curr+2, n, dp);
        return dp[curr];
    }

    int climbStairs(int n) {
        unordered_map<int, int> dp;
        return solve(0, n, dp);
    }
};
```

> Tabulationsolution - Accepted

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