Count ways to reach end from start stone with at most K jumps at each step | Function which returns total no . of ways to reach nth step from sth steps ; Initialize dp array ; 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
def TotalWays ( n , s , k ) : NEW_LINE INDENT dp = [ 0 ] * n NEW_LINE dp [ s - 1 ] = 1 NEW_LINE for i in range ( s , n ) : NEW_LINE INDENT idx = max ( s - 1 , i - k ) NEW_LINE for j in range ( idx , i ) : NEW_LINE INDENT dp [ i ] += dp [ j ] NEW_LINE DEDENT DEDENT return dp [ n - 1 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE k = 2 NEW_LINE s = 2 NEW_LINE print ( " Total ▁ Ways ▁ = ▁ " , TotalWays ( n , s , k ) ) NEW_LINE DEDENT