## Monday, May 16, 2022

### Easy_Question10 : Climbing Stairs

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: Brute-Force 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:
1. Taking a single step from `(i - 1)`th step
2. 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 on `i`th step, then
`dp[i] = dp[i - 1] + dp[i - 2]`

Time complexity: `O(n)`
Space Complexity: `O(n)`

Top-Down 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);
}
}``````

Bottom-Up 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 where `dp[i] = dp[i - 1] + dp[i - 2]`. It can be easily analyzed that `dp[i]` is nothing but `i`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 having `1` and `2` as their first and second term respectively,
i.e. `Fib(1) = 1` and `Fib(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;
}
}
``````

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS