DP-1 Climbing Stairs

Problem Link - 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

Intuition

• Initially we are at the ground let's say 0 as ground.
• From 0 we have to climb to the top of the steps. At each we can take either 1 or 2 steps from there.

*Approach *

• we will write a function that returns total number of distinct ways there are to reach step i. f(i)
• and so in our main function, we will call this function as f(n) which returns total numbers of ways to reach the top step n
• To reach a particular index i, we should be either at i-1th step or i-2th step (because we could reach ther by taking 1 step or 2 steps from the previous steps). so we will call both f(i-1) and f(i-2) in the function f(i) and return the sum of 2 recursive functions.
• and to reach i-1th step, we shoulb be either at i-2th step or i-3th step and so on..

• but we need to stop at one point, when we found valid solution, which is base case.
  Let’s determine in how many distinct ways we can climb to the top of a 4-step staircase.
  

• when we reach the 0th index which means at ground, so we found one valid solution.

• when we went to -1th index, which doesn't exist, we can say that there is no valid path that goes along that path.

so the base case could be when i=0 we will return 1.
and other possible case is when i<0(i.e i=-1) we will return 0, there is no possible way in this path.

Pseudo Code

f(i)
if(i==0) return 1
if(i<0) return 0
return f(i-1)+f(i-2)