Objective: A child is climbing up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can jump up the stairs.

Example:

Number of stairs : 3
Number of ways = 4 ( {1,1,1}, {1,2}, {2,1}, {3} )

Approach:

Say child has to take n steps.

At every step the child has 3 options, to take 1 step, 2 step or 3 steps.

So if child take 1 step then find the number of ways to complete n-1 steps +1.

Similarly if child take 2 steps then find the number of ways to complete n-2 steps +1.

If child take 3 step then find the number of ways to complete n-3 steps +1.

So total number of ways to complete n steps = No of ways to complete (n-1)steps + No of ways to complete (n-2)steps + No of ways to complete (n-3)steps +1.

Using Recursion:

If we solve this problem using recursion then all the sub-problems will be calculated repeatedly.

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Approavh should be updated to => So total number of ways to complete n steps = No of ways to complete (n-1)steps + No of ways to complete (n-2)steps + No of ways to complete (n-3)steps +1

tutorialhorizon

Thanks, updated it.

Antonio M

you are not using the dyn array to store anything. here is the solution.

public int poosibleWaysDyna(int n, int[] dyn) {
if (n 0) {
if (dyn[n]==0){
dyn[n] = 1 + poosibleWaysDyna(n – 1, dyn) + poosibleWaysDyna(n – 2, dyn)
+ poosibleWaysDyna(n – 3, dyn);
}
}
return dyn[n];
}

tutorialhorizon

Thanks Antonio for finding the miss, updated it

Harsh Shah

what is the +1 for ? shouldn’t the recurrence relation be dyn[n] = poosibleWaysDyna(n – 1, dyn) + poosibleWaysDyna(n – 2, dyn) + poosibleWaysDyna(n – 3, dyn);

tutorialhorizon

Hi Harsh,

+1 is for the step we are taken already. If you look at the recurrence relation, we are solving it for n-1, n-2, n-3. That means child has taken already one step (either 1 step or 2 step or 3 step and we are solving the remaining steps recursively). so we add +1. let me know if you need more clarity.

Jing

Why is not dyn[n] = poosibleWaysDyna(n – 1, dyn) + poosibleWaysDyna(n – 2, dyn) + poosibleWaysDyna(n – 3, dyn)+3? I mean 3 stands for the last step. It can be 1 step, 2 step2, or 3 step3 corresponding to poosibleWaysDyna(n – 1, dyn),poosibleWaysDyna(n – 2, dyn) and poosibleWaysDyna(n – 3, dyn) respectively. So the last step can have 3 types. Why do you consider 3 kinds of last step as only 1?

Sneha Deshpande

I need more clarification on why you have +1 at the end of the expression.

Soumitri Vadali

how is this dynamic at all? You are still recursively calling different functions. The whole idea is to save spae and time and that is not being done here in either approach.

tutorialhorizon

There are two approaches in dynamic programming, top-down and bottom-up. This is top-down (solve the smaller problem as needed and store result for future use, in bottom-up you break the problem in SMALLEST possible subproblem and store the result and keep solving it till you do not find the solution for the given problem. Please refer this link for more understanding.. http://algorithms.tutorialhorizon.com/introduction-to-dynamic-programming-fibonacci-series/

Ayushi

This gives incorrect output for n = 4.
There are only 7 possible ways for 4 stairs: 1111,112,121,211,13,31,22 but your solution gives the value 8.

Hou GuoChen

You do not +1 to the result. The recurrence relation is just ways(n-3) + ways(n-2) + ways(n-1).
In your approach, you are confusing the number of ways vs the additional step taken to reach N. Taking the additional step contributes to EACH of the step combination in each way, but does NOT contribute to the total number of ways it takes.

example:
First, let’s define the base cases for N=1,2,3 respectively.
Note: we are using alphabets to uniquely identify the actual combinations.

If N = 1, there’s 1 way to reach N.
the actual combinations are:
a. 1

if N=2, there’s 2 ways to reach N.
the actual combinations are:
b. 1,1
c. 2

if N=3, there’s 4 ways to reach N.
the actual combinations are:
d. 1,1,1
e. 1,2
f. 2,1
g. 3

Now when N=4, there will be 7 ways to reach N. The brackets in combinations below means the actual combinations we took from the case indicated in ‘possibleWays(N-1)’.

possibleWays(N-1) case:
(d. 1,1,1) + 1 = 1,1,1,1
(e. 1,2) + 1 = 1,2,1
(f. 2,1) + 1 = 2,1,1
(g. 3) + 1 = 3,1

As you can see above, the additional step (either 1,2,3) is the actual step required to take to complete each way to attain the new N and NOT an additional way.

vemurI krishna

exactly . It’s true

Alex

public static int getNumberOfPossibleWaysMath(int amount) {
if (amount <= 0) return 0;
if (amount <= 2) return amount;
if (amount == 3) return 4;

int minus3 = 1;
int minus2 = 2;
int minus1 = 4;
int curr = 0;
for(int i = 4; i <= amount; i++) {
curr = minus3 + minus2 + minus1;
minus3 = minus2;
minus2 = minus1;
minus1 = curr;
}
return curr;
}

Stretch

As the previous posters pointed out the formula used in this page is incorrect. For those that are still confused, this is the Tribonacci formula and works very similar to the Fibonacci DP (memoization) solution.
1. Trib(n) = Trib(n-1)+Trib(n-2)+Trib(n-3) (for n>=3)
2. seed the recursive function with base cases for n0=0, n1=1, n2=1.
3. Use memoization to store results of previous numbers.
The sequence goes something like 0,1,1,2,4,7,13,24,44,81….

vaibhav shah

If anyone is looking for a return type Long.

public Long possibleWaysDyna(int n, Long [] dyn) {
if (n 0) {
return dyn[n];
}
dyn[n] = 1 + possibleWaysDyna(n – 1, dyn) + possibleWaysDyna(n – 2, dyn)
;
return dyn[n];
}

dheeraj singhal

Solution is not correct.Your solution for 4 steps will return 8 but correct answer is 7.Below is correct one.

public int countSteps(int n){
if(n==0){
return 1;
}
if(n<0){
return 0;
}
return countSteps(n-1)+countSteps(n-2)+countSteps(n-3);
}