We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Note that we need to pass a hashmap before calling the function in the loop for each staircase.
I created this simple diagram for you to see the idea more clearly if you had any questions 😉
Number of ways to climb a staircase
possible jumps are 1 2 3 stairs
Important to notice that A(n) = A(n-3) + A(n-2) + A(n-1) being A(n) the NUMBER OF WAYS to clib a staircase of n stairs.
Let's see why this series approach works with an example:
Imagine we are trying to compute 4 from 3, 2 & 1.
When we sum we are saying basically that there are 3+2+1 ways to end up in a step of the staircase that is in a one step reachable distance to the step we are trying to reach in this case step of height 4.
We can jump from step 1 with a jump of distance 3 to get to 4. Since there is only one combination to get to staircase 1, this adds up only 1 to our final result
We can jump from step 2 with a jump of 2 to get to 4 . There are 2 ways to get to step 2 so it adds up 2 to the final result
We can jump from step 3 with a jump of 1 to get to 4. There are 4 ways to get to step 3 so it adds up 4 to the final result
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Recursion: Davis' Staircase
You are viewing a single comment's thread. Return to all comments →
Java solution
PASSES 100% OF TEST CASES ✅
O(N) TIME COMPLEXITY
O(1) SPACE COMPLEXITY
Dude... just memoize as it is done in optimizing a classic Fibo problem! 😁
I created this simple diagram for you to see the idea more clearly if you had any questions 😉
Number of ways to climb a staircase
possible jumps are 1 2 3 stairs
Let's see why this series approach works with an example:
Imagine we are trying to compute 4 from 3, 2 & 1.
When we sum we are saying basically that there are 3+2+1 ways to end up in a step of the staircase that is in a one step reachable distance to the step we are trying to reach in this case step of height 4.