A frog is jumping 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 frog can run up the stairs.
We will be using recursive approach first to solve this problem
public class StepsCountDP {
private static int DiffJumpsCount(int totalStairs) {
if(totalStairs == 0)
return 1;
else if(totalStairs == 1)
return 1;
else if(totalStairs == 2)
return 2;
else
return DiffJumpsCount(totalStairs-1) +
DiffJumpsCount(totalStairs - 2) +
DiffJumpsCount(totalStairs - 3);
}
public static void main(String[] args) {
int totalStairs = 4;
System.out.println(DiffJumpsCount(totalStairs));
}
}
We can store the previously computed result as well in the above case to make it more optimized.
The Dynamic Programming Approach for the above problem is below :
public class StepsCountDP {
private static int DiffJumpsCount(int totalStairs) {
int[] arr = new int[totalStairs+1];
arr[0] = 1;
arr[1] = 1;
arr[2] = 2;
for(int i= 3 ; i< totalStairs+1;i++) {
arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
}
return arr[totalStairs];
}
public static void main(String[] args) {
int totalStairs = 4;
System.out.println(DiffJumpsCount(totalStairs));
}
}
Output :
7
