Staircase Problem

A child going up a staircase with n steps, can hop up 1, 2, or 3 steps at a time. How many ways can the child reach the top?

Solution:

• It very similar to Fibonacci problem
• So, formula S(n) = S(n-1) + S(n-2) + S(n-3)
• Can be easily solved by recursion but runtime complexity could be O(3^n)
• We can you dynamic programming (memoization) and with this it will be O(n)

Algorithm:

1. Base case : When n < 0 then return 0
2. Base case: When n == 0 then return 1
3. When n is already computed then return computed value
4. Else compute(n) = compute(n-1) + compute(n-2) + compute(n-3)
5. Store computed value in auxiliary memory and return the same.

Latest Source Code:
Github: StaircaseProblem.java

Output:

(Top Down) When n == 1 then, count = 1
(Bottom Up) When n == 1 then, count = 1
(Optimised) When n == 1 then, count = 1

(Top Down) When n == 2 then, count = 2
(Bottom Up) When n == 2 then, count = 2
(Optimised) When n == 1 then, count = 2

(Top Down) When n == 3 then, count = 4
(Bottom Up) When n == 3 then, count = 4
(Optimised) When n == 1 then, count = 4

(Top Down) When n == 4 then, count = 7
(Bottom Up) When n == 4 then, count = 7
(Optimised) When n == 1 then, count = 7

(Top Down) When n == 5 then, count = 13
(Bottom Up) When n == 5 then, count = 13
(Optimised) When n == 1 then, count = 13

(Top Down) When n == 6 then, count = 24
(Bottom Up) When n == 6 then, count = 24
(Optimised) When n == 1 then, count = 24

(Top Down) When n == 7 then, count = 44
(Bottom Up) When n == 7 then, count = 44
(Optimised) When n == 1 then, count = 44

Video

Quora