Given an array arr[] of N integers and an integer K, one can move from an index i to any other j if j ? i + k. The cost of moving from one index i to the other index j is abs(arr[i] – arr[j]). Initially, we start from the index 0 and we need to reach the last index i.e. N – 1. The task is to reach the last index in the minimum cost possible.
Examples:
Input: arr[] = {10, 30, 40, 50, 20}, k = 3
Output: 30
0 -> 1 -> 4
the total cost will be: |10-30| + |30-20| = 30
Input: arr[] = {40, 10, 20, 70, 80, 10}, k = 4
Output: 30
Approach 1: The problem can be solved using Dynamic Programming. We start from index 0 and we can visit any of the indexes from i+1 to i+k, hence the minimum cost of all the paths will be stored in dp[i]. Once we reach N-1, it will be our base case. Use memoization to memoize the states, so that we do not need to revisit the state again to reduce complexity.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum cost// to reach the last indexint FindMinimumCost(int ind, int a[], int n, int k, int dp[]){ // If we reach the last index if (ind == (n - 1)) return 0; // Already visited state else if (dp[ind] != -1) return dp[ind]; else { // Initially maximum int ans = INT_MAX; // Visit all possible reachable index for (int i = 1; i <= k; i++) { // If inside range if (ind + i < n) ans = min(ans, abs(a[ind + i] - a[ind]) + FindMinimumCost(ind + i, a, n, k, dp)); // We cannot move any further else break; } // Memoize return dp[ind] = ans; }}// Driver Codeint main(){ int a[] = { 10, 30, 40, 50, 20 }; int k = 3; int n = sizeof(a) / sizeof(a[0]); int dp[n]; memset(dp, -1, sizeof dp); cout << FindMinimumCost(0, a, n, k, dp); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GfG { // Function to return the minimum cost // to reach the last index static int FindMinimumCost(int ind, int a[], int n, int k, int dp[]) { // If we reach the last index if (ind == (n - 1)) return 0; // Already visited state else if (dp[ind] != -1) return dp[ind]; else { // Initially maximum int ans = Integer.MAX_VALUE; // Visit all possible reachable index for (int i = 1; i <= k; i++) { // If inside range if (ind + i < n) ans = Math.min(ans, Math.abs(a[ind + i] - a[ind]) + FindMinimumCost(ind + i, a, n, k, dp)); // We cannot move any further else break; } // Memoize return dp[ind] = ans; } } // Driver Code public static void main(String[] args) { int a[] = { 10, 30, 40, 50, 20 }; int k = 3; int n = a.length; int dp[] = new int[n]; Arrays.fill(dp, -1); System.out.println(FindMinimumCost(0, a, n, k, dp)); }} // This code is contributed by Prerna Saini |
Python3
# Python 3 implementation of the approachimport sys# Function to return the minimum cost# to reach the last indexdef FindMinimumCost(ind, a, n, k, dp): # If we reach the last index if (ind == (n - 1)): return 0 # Already visited state elif (dp[ind] != -1): return dp[ind] else: # Initially maximum ans = sys.maxsize # Visit all possible reachable index for i in range(1, k + 1): # If inside range if (ind + i < n): ans = min(ans, abs(a[ind + i] - a[ind]) + FindMinimumCost(ind + i, a, n, k, dp)) # We cannot move any further else: break # Memoize dp[ind] = ans return ans# Driver Codeif __name__ == '__main__': a = [10, 30, 40, 50, 20] k = 3 n = len(a) dp = [-1 for i in range(n)] print(FindMinimumCost(0, a, n, k, dp))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the above approachusing System;class GfG { // Function to return the minimum cost // to reach the last index static int FindMinimumCost(int ind, int []a, int n, int k, int []dp) { // If we reach the last index if (ind == (n - 1)) return 0; // Already visited state else if (dp[ind] != -1) return dp[ind]; else { // Initially maximum int ans = int.MaxValue; // Visit all possible reachable index for (int i = 1; i <= k; i++) { // If inside range if (ind + i < n) ans = Math.Min(ans, Math.Abs(a[ind + i] - a[ind]) + FindMinimumCost(ind + i, a, n, k, dp)); // We cannot move any further else break; } // Memoize return dp[ind] = ans; } } // Driver Code public static void Main() { int []a = { 10, 30, 40, 50, 20 }; int k = 3; int n = a.Length; int []dp = new int[n]; for(int i = 0; i < n ; i++) dp[i] = -1 ; Console.WriteLine(FindMinimumCost(0, a, n, k, dp)); }}// This code is contributed by Ryuga |
PHP
<?php// PHP implementation of the approach// Function to return the minimum cost // to reach the last index function FindMinimumCost($ind, $a, $n, $k, $dp) { // If we reach the last index if ($ind == ($n - 1)) return 0; // Already visited state else if ($dp[$ind] != -1) return $dp[$ind]; else { // Initially maximum $ans = PHP_INT_MAX; // Visit all possible reachable index for ($i = 1; $i <= $k; $i++) { // If inside range if ($ind + $i < $n) $ans = min($ans, abs($a[$ind + $i] - $a[$ind]) + FindMinimumCost($ind + $i, $a, $n, $k, $dp)); // We cannot move any further else break; } // Memoize return $dp[$ind] = $ans; } } // Driver Code $a = array(10, 30, 40, 50, 20 ); $k = 3; $n = sizeof($a); $dp = array(); $dp = array_fill(0, $n, -1); echo(FindMinimumCost(0, $a, $n, $k, $dp)); // This code is contributed by Code_Mech.?> |
Javascript
<script>// JavaScript implementation of the approach // Function to return the minimum cost // to reach the last index function FindMinimumCost(ind , a , n , k , dp) { // If we reach the last index if (ind == (n - 1)) return 0; // Already visited state else if (dp[ind] != -1) return dp[ind]; else { // Initially maximum var ans = Number.MAX_VALUE; // Visit all possible reachable index for (var i = 1; i <= k; i++) { // If inside range if (ind + i < n) ans = Math.min(ans, Math.abs(a[ind + i] - a[ind]) + FindMinimumCost(ind + i, a, n, k, dp)); // We cannot move any further else break; } // Memoize return dp[ind] = ans; } } // Driver Code var a = [ 10, 30, 40, 50, 20]; var k = 3; var n = a.length; var dp = Array(n).fill(-1); document.write(FindMinimumCost(0, a, n, k, dp));// This code contributed by aashish1995</script> |
Output:
30
Time Complexity: O(N * K)
Auxiliary Space: O(N)
Approach 2:
The second approach also requires the use of Dynamic programming. This approach is based on Bellman ford’s DP solution to the single-source shortest path. In Bellman’s ford SSSP, the main idea is to find the next vertex through minimizing on edges, we can do the same we minimize on abs values of two elements of an array to find the next index.
For solving any DP problems we first guess all the possible solutions to the subproblems and memoize them then choose the best solutions to the subproblem. we write Recurrence for the problem
Recurrence: DP(j) = min{DP(i) + abs(A[i] – A[j])} where i is in [0, N-1] and j is in [i + 1, j + k + 1], and k is number of jumps allowed. this can also be compared with relaxation in SSSP. We are going to relax every next approachable index.
// base case
memo[0] = 0;
for (i = 0 to N-1)
for (j = i+1 to i+k+1)
memo[j] = min(memo[j], memo[i] + abs(A[i] – A[j]));
Below is the implementation of the Bottom-up above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function for returning the min of two elementsint min(int a, int b) { return (a > b) ? b : a;}int minCostJumpsDP(vector <int> & A, int k) { // for calculating the number of elements int size = A.size(); // Allocating Memo table and // initializing with INT_MAX vector <int> x(size, INT_MAX); // Base case x[0] = 0; // For every element relax every reachable // element ie relax next k elements for (int i = 0; i < size; i++) { // reaching next k element for (int j = i + 1; j < i + k + 1; j++) { // Relaxing the element x[j] = min(x[j], x[i] + abs(A[i] - A[j])); } } // return the last element in the array return x[size - 1];}// Driver Codeint main(){ vector <int> input { 83, 26, 37, 35, 33, 35, 56 }; cout << minCostJumpsDP(input, 3); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function for returning the// min of two elementsstatic int min(int a, int b){ return (a > b) ? b : a;}static int minCostJumpsDP(int []A, int k){ // for calculating the number of elements int size = A.length; // Allocating Memo table and // initializing with INT_MAX int []x = new int[size]; Arrays.fill(x, Integer.MAX_VALUE); // Base case x[0] = 0; // For every element relax every reachable // element ie relax next k elements for (int i = 0; i < size; i++) { // reaching next k element for (int j = i + 1; j < i + k + 1 && j < size; j++) { // Relaxing the element x[j] = min(x[j], x[i] + Math.abs(A[i] - A[j])); } } // return the last element in the array return x[size - 1];}// Driver Codepublic static void main(String []args) { int []input = { 83, 26, 37, 35, 33, 35, 56 }; System.out.println(minCostJumpsDP(input, 3));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach import sysdef minCostJumpsDP(A, k): # for calculating the number of elements size = len(A) # Allocating Memo table and # initializing with INT_MAX x = [sys.maxsize] * (size) # Base case x[0] = 0 # For every element relax every reachable # element ie relax next k elements for i in range(size): # reaching next k element j = i+1 while j < i + k + 1 and j < size: # Relaxing the element x[j] = min(x[j], x[i] + abs(A[i] - A[j])) j += 1 # return the last element in the array return x[size - 1] # Driver Code if __name__ == "__main__": input_ = [83, 26, 37, 35, 33, 35, 56] print(minCostJumpsDP(input_, 3)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System;class GFG{// Function for returning the// min of two elementsstatic int min(int a, int b){ return (a > b) ? b : a;}static int minCostJumpsDP(int []A, int k){ // for calculating the number of elements int size = A.Length; // Allocating Memo table and // initializing with INT_MAX int []x = new int[size]; for (int i = 0; i < size; i++) x[i] = int.MaxValue; // Base case x[0] = 0; // For every element relax every reachable // element ie relax next k elements for (int i = 0; i < size; i++) { // reaching next k element for (int j = i + 1; j < i + k + 1 && j < size; j++) { // Relaxing the element x[j] = min(x[j], x[i] + Math.Abs(A[i] - A[j])); } } // return the last element in the array return x[size - 1];}// Driver Codepublic static void Main(String []args) { int []input = { 83, 26, 37, 35, 33, 35, 56 }; Console.WriteLine(minCostJumpsDP(input, 3));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the approach // Function for returning the // min of two elements function min(a, b) { return (a > b) ? b : a; } function minCostJumpsDP(A, k) { // for calculating the number of elements let size = A.length; // Allocating Memo table and // initializing with INT_MAX let x = new Array(size); for (let i = 0; i < size; i++) x[i] = Number.MAX_VALUE; // Base case x[0] = 0; // For every element relax every reachable // element ie relax next k elements for (let i = 0; i < size; i++) { // reaching next k element for (let j = i + 1; j < i + k + 1 && j < size; j++) { // Relaxing the element x[j] = min(x[j], x[i] + Math.abs(A[i] - A[j])); } } // return the last element in the array return x[size - 1]; } let input = [ 83, 26, 37, 35, 33, 35, 56 ]; document.write(minCostJumpsDP(input, 3)); </script> |
Output:
69
Time Complexity: O(N * K)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
