Number of ways to reach Nth floor by taking at-most K leaps in Java
Determining the number of unique ways to climb a staircase with N steps from the bottom, given an integer K denoting the maximum number of steps that may be taken in a single move (leap). At most K leaps must be made in one motion to climb each step.
Example 1:
Input: N = 4
K = 2
Output: Number of ways to climb to the top in at most 2 leaps: 3
Explanation: 1 1 1 1
1 1 2
2 2
1 1 1 1: This stands for taking one step at a time up each staircase. In this instance, the individual makes four leaps, one for each step.
1 1 2: The subject makes two leaps at this point. They climb two steps in their first leap and one step in their second. All four steps are covered in this.
2 2: In this instance, the individual makes two jumps, each of which covers two paces. All four steps are included in this.
These combinations exhaust all possibilities within the limit of two leaps.
Example 2:
Input: N = 10
K = 4
Output: Number of ways to climb to the top in at most 4 leaps: 23
Explanation: 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 2 2
1 1 1 1 2 2 2 and all the combinations upto K=4 which give sum 10.
There are a total of 23 unique methods to climb the steps.
Approach: Iterative
This Java method iteratively determines the number of ways to ascend a staircase with N steps and a maximum of K leaps. It creates an array (ways) to track ways for each step, with the default value of one way for 0 stairs. The nested loops update ways based on previous results, and the final output shows the computed ways to reach the summit with at most K leaps.
FileName: WaysToClimbStairs.java
public class WaysToClimbStairs {
public static void main(String args[]) {
int N = 10; // Total stairs
int K = 4; // Maximum leaps
// Array to store the number of possible ways to climb each stair
int[] ways = new int[N + 1];
ways[0] = 1; // There is 1 way to climb 0 stairs (base case)
int leap = 1;
// Iterating through possible leaps
while (leap <= K) {
int stair = 0;
// Iterating through all stairs
while (stair <= N) {
if (stair >= leap) {
ways[stair] += ways[stair - leap];
}
stair++;
}
leap++;
}
// Printing the number of ways to climb to the top in at most K leaps
System.out.println("Number of ways to climb to the top in at most " + K + " leaps: " + ways[N]);
}
}
Output:
Number of ways to climb to the top in at most 4 leaps: 23
Complexity Analysis: The time complexity is O(N * K) due to the nested iterations through all possible combinations of stairs and leaps. The array that stores the number of ways for each stair has a space complexity of O(N).
Approach: Dynamic Programming
The code uses a dynamic programming approach to calculate the number of ways to climb a staircase with N stairs and at most K leaps. It stores intermediate results in a 2D array (dp), with each entry dp[stair][leap] representing the precise number of leaps required to reach the stair. The function iterates through all conceivable combinations of stairs and jumps, updating the dp array with previously computed values. The base case is established for the 0th stair, ensuring that there is only one route to get there. The ultimate result, recorded in dp[N][K], represents the total number of ways to reach the top with at most K leaps.
FileName: WaysToClimbStairs1.java
public class WaysToClimbStairs1 {
public static int countWaysToClimbStairs(int N, int K) {
int[][] dp = new int[N + 1][K + 1];
for (int stair = 0; stair <= N; stair++) {
for (int leap = 1; leap <= K; leap++) {
if (stair == 0) {
dp[stair][leap] = 1; // Base case: there is one way to reach the 0th stair
} else {
if (stair - leap >= 0) {
dp[stair][leap] = dp[stair - leap][leap] + dp[stair][leap - 1];
} else {
dp[stair][leap] = dp[stair][leap - 1];
}
}
}
}
return dp[N][K];
}
public static void main(String[] args) {
int N = 10; // Total stairs
int K = 4; // Maximum leaps
int result = countWaysToClimbStairs(N, K);
// Output the result
System.out.println("Number of ways to climb to the top in at most " + K + " leaps: " + result);
}
}
Output:
Number of ways to climb to the top in at most 4 leaps: 23
Complexity Analysis: The provided code has a temporal complexity of O(N * K) due to the nested loops that iterate through all combinations of stairs and leaps. The space complexity is also O(N * K), as intermediate results must be stored in a 2D array.