Given N stones in a row from left to right. From each stone, you can jump to at most K stones. The task is to find the total number of ways to reach from sth stone to Nth stone.
Examples:
Input: N = 5, s = 2, K = 2
Output: Total Ways = 3
Explanation:
Assume s1, s2, s3, s4, s5 be the stones. The possible paths from 2nd stone to 5th stone:
s2 -> s3 -> s4 -> s5
s2 -> s4 -> s5
s2 -> s3 -> s5
Hence total number of ways = 3
Input: N = 8, s = 1, K = 3
Output: Total Ways = 44
Approach:
- Let assume dp[i] be the number of ways to reach ith stone.
- Since there are atmost K jumps, So the ith stone can be reach by all it’s previous K stones.
- Iterate for all possible K jumps and keep adding this possible combination to the array dp[].
- Then the total number of possible ways to reach Nth node from sth stone will be dp[N-1].
- For Example:
Let N = 5, s = 2, K = 2, then we have to reach Nth stone from sth stone.
Let dp[N+1] is the array that stores the number of paths to reach the Nth Node from sth stone.
Initially, dp[] = { 0, 0, 0, 0, 0, 0 } and dp[s] = 1, then
dp[] = { 0, 0, 1, 0, 0, 0 }
To reach the 3rd,
There is only 1 way with at most 2 jumps i.e., from stone 2(with jump = 1). Update dp[3] = dp[2]
dp[] = { 0, 0, 1, 1, 0, 0 }
To reach the 4th stone,
The two ways with at most 2 jumps i.e., from stone 2(with jump = 2) and stone 3(jump = 1). Update dp[4] = dp[3] + dp[2]
dp[] = { 0, 0, 1, 1, 2, 0 }
To reach the 5th stone,
The two ways with at most 2 jumps i.e., from stone 3(with jump = 2) and stone 4(with jump = 1). Update dp[5] = dp[4] + dp[3]
dp[] = { 0, 0, 1, 1, 2, 3 }
Now dp[N] = 3 is the number of ways to reach Nth stone from sth stone.
Below is the implementation of the above approach:
C++
// C++ program to find total no.of ways// to reach nth step#include "bits/stdc++.h"using namespace std;// Function which returns total no.of ways// to reach nth step from sth stepsint TotalWays(int n, int s, int k){ // Initialize dp array with 0s. vector<int> dp(n,0); // Initialize (s-1)th index to 1 dp[s - 1] = 1; // Iterate a loop from s to n for (int i = s; i < n; i++) { // starting range for counting ranges int idx = max(s - 1, i - k); // Calculate Maximum moves to // Reach ith step for (int j = idx; j < i; j++) { dp[i] += dp[j]; } } // For nth step return dp[n-1] return dp[n - 1];}// Driver Codeint main(){ // no of steps int n = 5; // Atmost steps allowed int k = 2; // starting range int s = 2; cout << "Total Ways = " << TotalWays(n, s, k);} |
Java
// Java program to find total no.of ways// to reach nth stepclass GFG{ // Function which returns total no.of ways// to reach nth step from sth stepsstatic int TotalWays(int n, int s, int k){ // Initialize dp array int []dp = new int[n]; // Initialize (s-1)th index to 1 dp[s - 1] = 1; // Iterate a loop from s to n for (int i = s; i < n; i++) { // starting range for counting ranges int idx = Math.max(s - 1, i - k); // Calculate Maximum moves to // Reach ith step for (int j = idx; j < i; j++) { dp[i] += dp[j]; } } // For nth step return dp[n-1] return dp[n - 1];} // Driver Codepublic static void main(String[] args){ // no of steps int n = 5; // Atmost steps allowed int k = 2; // starting range int s = 2; System.out.print("Total Ways = " + TotalWays(n, s, k));}}// This code is contributed by sapnasingh4991 |
Python3
# Python 3 program to find total no.of ways# to reach nth step# Function which returns total no.of ways# to reach nth step from sth stepsdef TotalWays(n, s, k): # Initialize dp array dp = [0]*n # Initialize (s-1)th index to 1 dp[s - 1] = 1 # Iterate a loop from s to n for i in range(s, n): # starting range for counting ranges idx = max(s - 1, i - k) # Calculate Maximum moves to # Reach ith step for j in range( idx, i) : dp[i] += dp[j] # For nth step return dp[n-1] return dp[n - 1]# Driver Codeif __name__ == "__main__": # no of steps n = 5 # Atmost steps allowed k = 2 # starting range s = 2 print("Total Ways = ", TotalWays(n, s, k)) # This code is contributed by chitranayal |
C#
// C# program to find total no.of ways// to reach nth stepusing System;class GFG{ // Function which returns total no.of ways // to reach nth step from sth steps static int TotalWays(int n, int s, int k) { // Initialize dp array int []dp = new int[n]; // Initialize (s-1)th index to 1 dp[s - 1] = 1; // Iterate a loop from s to n for (int i = s; i < n; i++) { // starting range for counting ranges int idx = Math.Max(s - 1, i - k); // Calculate Maximum moves to // Reach ith step for (int j = idx; j < i; j++) { dp[i] += dp[j]; } } // For nth step return dp[n-1] return dp[n - 1]; } // Driver Code public static void Main(string[] args) { // no of steps int n = 5; // Atmost steps allowed int k = 2; // starting range int s = 2; Console.Write("Total Ways = "+ TotalWays(n, s, k)); }}// This code is contributed by Yash_R |
Javascript
<script>// Javascript program to find total no.of ways// to reach nth step// Function which returns total no.of ways// to reach nth step from sth stepsfunction TotalWays(n, s, k){ // Initialize dp array let dp = new Array(n); // filling all the elements with 0 dp.fill(0); // Initialize (s-1)th index to 1 dp[s - 1] = 1; // Iterate a loop from s to n for (let i = s; i < n; i++) { // starting range for counting ranges let idx = Math.max(s - 1, i - k); // Calculate Maximum moves to // Reach ith step for (let j = idx; j < i; j++) { dp[i] += dp[j]; } } // For nth step return dp[n-1] return dp[n - 1];}// Driver Code // no of steps let n = 5; // Atmost steps allowed let k = 2; // starting range let s = 2; document.write("Total Ways = " + TotalWays(n, s, k)); // This code is contributed by _saurabh_jaiswal</script> |
Total Ways = 3
Time Complexity: O(N*K), where N is the number of stones, k is maximum jump range.
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
