Minimum cost to reach end of array array when a maximum jump of K index is allowed | Python 3 implementation of the approach ; Function to return the minimum cost to reach the last index ; If we reach the last index ; Already visited state ; Initially maximum ; Visit all possible reachable index ; If inside range ; We cannot move any further ; Memoize ; Driver Code
import sys NEW_LINE def FindMinimumCost ( ind , a , n , k , dp ) : NEW_LINE INDENT if ( ind == ( n - 1 ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( dp [ ind ] != - 1 ) : NEW_LINE INDENT return dp [ ind ] NEW_LINE DEDENT else : NEW_LINE INDENT ans = sys . maxsize NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT if ( ind + i < n ) : NEW_LINE INDENT ans = min ( ans , abs ( a [ ind + i ] - a [ ind ] ) + FindMinimumCost ( ind + i , a , n , k , dp ) ) NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT dp [ ind ] = ans NEW_LINE return ans NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 10 , 30 , 40 , 50 , 20 ] NEW_LINE k = 3 NEW_LINE n = len ( a ) NEW_LINE dp = [ - 1 for i in range ( n ) ] NEW_LINE print ( FindMinimumCost ( 0 , a , n , k , dp ) ) NEW_LINE DEDENT