easy
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 space
O(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;
}
};