Count ways to reach end from start stone with at most K jumps at each step | C ++ program to find total no . of ways to reach nth step ; Function which returns total no . of ways to reach nth step from sth steps ; Initialize dp array ; filling all the elements with 0 ; Initialize ( s - 1 ) th index to 1 ; Iterate a loop from s to n ; starting range for counting ranges ; Calculate Maximum moves to Reach ith step ; For nth step return dp [ n - 1 ] ; Driver Code ; no of steps ; Atmost steps allowed ; starting range
#include " bits / stdc + + . h " NEW_LINE using namespace std ; int TotalWays ( int n , int s , int k ) { int dp [ n ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ s - 1 ] = 1 ; for ( int i = s ; i < n ; i ++ ) { int idx = max ( s - 1 , i - k ) ; for ( int j = idx ; j < i ; j ++ ) { dp [ i ] += dp [ j ] ; } } return dp [ n - 1 ] ; } int main ( ) { int n = 5 ; int k = 2 ; int s = 2 ; cout << " Total ▁ Ways ▁ = ▁ " << TotalWays ( n , s , k ) ; }