Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Solution: Staircase

Problem Statement

Given a stair with 'n' steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps.

Example 1:

Number of stairs (n) : 3
Number of ways = 4
Explanation: Following are the four ways we can climb : {1,1,1}, {1,2}, {2,1}, {3}

Example 2:

Number of stairs (n) : 4
Number of ways = 7
Explanation: Following are the seven ways we can climb : {1,1,1,1}, {1,1,2}, {1,2,1}, {2,1,1}, 
{2,2}, {1,3}, {3,1}

Constraints:

  • 1 <= n <= 45

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Sreeraj Punnoli

· 4 years ago

For n == 0, "base case, we don't need to take any step, so there is only one way". Why is it like that? If n is 0, there is no stairs and no way. Why is the result 1 for n ==0?

Show 1 reply
S

Sarah

· 3 years ago

These solutions all seem to fail on various cases when the code is run - is anyone else having issues?

Show 1 reply