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
Solution 1: BruteForce Approach
Base cases:
if n == 0
, then the number of ways should be zero
.
if n == 1
, then there is only one
way to climb the stair.
if n == 2
, then there are two
ways to climb the stairs. One solution is one
step by another; the other one is two
steps at one time.

We can reach
i
th step in one of the two ways:

Taking a single step from
(i  1)
th step 
Taking a step of two from
(i  2)
th step.

So, the total number of ways to reach
i
th step is equal to sum of ways of reaching(i  1)
th step and ways of reaching(i  2)
th step.
Time complexity: O(2^n)
 since size of recursion tree will be 2^n
Space Complexity: O(n)
 space required for the recursive function call stack.
class Solution { public int climbStairs(int n) { if(n <= 2) return n; else return climbStairs(n  1) + climbStairs(n  2); } }
Solution 2: Dynamic Programming

This similar to
Solution1
, but here we cache the intermediate results in an array for the performance improvement. 
Let
dp[i]
denotes the number of ways to reach oni
th step, thendp[i] = dp[i  1] + dp[i  2]
Time complexity: O(n)
Space Complexity: O(n)
TopDown Approach
class Solution { int[] cache = new int[46]; public int climbStairs(int n) { if(n <= 2) return n; else if(cache[n] != 0) return cache[n]; else return cache[n] = climbStairs(n  1) + climbStairs(n  2); } }
BottomUp Approach:
class Solution { public int climbStairs(int n) { if(n <= 2) return n; int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) { dp[i] = dp[i  1] + dp[i  2]; } return dp[n]; } }
Solution 3: Fibonacci Number

In the above approach of
Solution2
, we have used an array wheredp[i] = dp[i  1] + dp[i  2]
. It can be easily analyzed thatdp[i]
is nothing buti
th Fibonacci number.Fib(n) = Fib(n  1) + Fib(n  2)

So now we just have to find
n
th number of the Fibonacci series having1
and2
as their first and second term respectively,
i.e.Fib(1) = 1
andFib(2) = 2
.
Time complexity: O(n)
Space Complexity: O(1)
class Solution { public int climbStairs(int n) { if(n <= 2) return n; int a = 1; int b = 2; for(int i = 3; i <= n; i++) { int sum = a + b; a = b; b = sum; } return b; } }