**source:**https://leetcode.com/problems/climbing-stairs/**C/C++**

**Solution to LeetCode**problem

**70**.

**Climbing Stairs**.

## Problem

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?

## Examples

**Example 1:**

Input:n = 2

Output:2

Explanation:There are two ways to climb to the top.

- 1 step + 1 step
- 2 steps

**Example 2:**

Input:n = 3

Output:3

Explanation:There are three ways to climb to the top.

- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step

## Constraints

`1 <= n <= 45`

## Solution

This can be solved in two ways:

- With
**Dynamic Programing**. (This one requires spaceO(n)</code>). - The Fibonacci sequence.

### Solution 1 (Dynamic Programming)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
int solve(int n, vector<int> &dp){
if (n<=2)
return n;
if (dp[n] != -1)
return dp[n];
dp[n] = solve(n-1, dp) + solve(n-2, dp);
return dp[n];
}
int climbStairs(int n) {
if(n<=2)
return n;
vector<int> dp(n+1, -1);
return solve(n, dp);
}
};

### Solution 2 (Fibonacci Sequence)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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