Minimum cost to reach end of array array when a maximum jump of K index is allowed | C ++ implementation of the approach ; Function for returning the min of two elements ; for calculating the number of elements ; Allocating Memo table and initializing with INT_MAX ; Base case ; For every element relax every reachable element ie relax next k elements ; reaching next k element ; Relaxing the element ; return the last element in the array ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int min ( int a , int b ) { return ( a > b ) ? b : a ; } int minCostJumpsDP ( vector < int > & A , int k ) { int size = A . size ( ) ; vector < int > x ( size , INT_MAX ) ; x [ 0 ] = 0 ; for ( int i = 0 ; i < size ; i ++ ) { for ( int j = i + 1 ; j < i + k + 1 ; j ++ ) { x [ j ] = min ( x [ j ] , x [ i ] + abs ( A [ i ] - A [ j ] ) ) ; } } return x [ size - 1 ] ; } int main ( ) { vector < int > input { 83 , 26 , 37 , 35 , 33 , 35 , 56 } ; cout << minCostJumpsDP ( input , 3 ) ; return 0 ; }