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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class StepsPossiblePathsRecur { | |
| public int possibleWays(int n) { | |
| if (n < 1) { | |
| return 0; | |
| } | |
| return 1 + possibleWays(n – 1) + possibleWays(n – 2) | |
| + possibleWays(n – 3); | |
| } | |
| public static void main(String[] args) { | |
| // TODO Auto-generated method stub | |
| int n = 3; | |
| StepsPossiblePathsRecur s = new StepsPossiblePathsRecur(); | |
| System.out.println(s.possibleWays(n)); | |
| } | |
| } |
If we solve this problem using recursion then all the sub-problems will be calculated repeatedly.
Using Dynamic Programming:
- We will solve it Top-Down approach.
- We need to store the solutions for the sub problems in an array.
DP Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class StepsPossiblePathsRecur { | |
| public int possibleWaysDyna(int n, int[] dyn) { | |
| if (n == 0) | |
| return 1; | |
| if (n < 0) | |
| return 0; | |
| if (dyn[n] > 0) { | |
| return dyn[n]; | |
| } | |
| dyn[n] = possibleWaysDyna(n – 1, dyn) + possibleWaysDyna(n – 2, dyn) | |
| + possibleWaysDyna(n – 3, dyn); | |
| return dyn[n]; | |
| } | |
| public static void main(String[] args) { | |
| // TODO Auto-generated method stub | |
| int n = 3; | |
| StepsPossiblePathsRecur s = new StepsPossiblePathsRecur(); | |
| int[] dyn = new int[n + 1]; | |
| System.out.println(s.possibleWaysDyna(n, dyn)); | |
| } | |
| } |
Output:
4
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
Thanks, updated it.
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];
}
Thanks Antonio for finding the miss, updated it
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);
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.
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?
I need more clarification on why you have +1 at the end of the expression.
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.
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/
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.
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
possibleWays(N-2) case:
(b. 1,1) + 2 = 1,1,2
(c. 2) + 2 = 2,2
possibleWays(N-3) case:
(a. 1) + 3 = 1,3
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.
exactly . It’s true
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;
}
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….
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];
}
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);
}