Minimum Cost to Reach End

Posted: 27 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

You are given an array “ARR” of 'N' integers and an integer 'K'. You can move from any index 'i' to index 'j' if j ≤ i + K. The cost of moving from one index 'i' to the other index 'j' is abs(ARR[j] – ARR[i]). Your task is to find the minimum cost to reach the end of the array from the beginning of the array when a maximum jump of 'K' is allowed.

For example:
``````If the given array is [10, 3, 40, 5, 25] and K is 2 then the minimum cost would be 29.
Since K = 2, the optimal way to reach the end of the array with minimum cost is to take a jump to 1st index from 0th index with the cost of abs(3 - 10)  i.e 7 and then we take a jump of 2 from 1st index to the 3rd index with the cost of abs(5 - 3). i.e 2. Then we take a jump of 1 from 3rd index to the last index with the cost of abs(25 - 5) .ie 20.
Therefore the minimum cost to reach the end of the array is (7 + 2 + 20) i.e 29.
``````
Input format :
``````The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.

The first line of each test case contains two single space-separated integers 'N', and 'K', denoting the size of the array and the maximum jump allowed from any index.

The second line of each test case contains 'N' single space-separated integers, elements of the array.
``````
Output format :
``````For each test case, print a single line containing a single integer denoting the minimum cost, in a single line.

The output of each test case will be printed in a separate line.
``````

Note:

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
Constraints :
``````1 <= T <= 10
2 <= N <= 1000
1 <= K < N
0 <= ARR[i] <= 10 ^ 6

Time Limit: 1 sec.
``````
Approach 1

The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. In this, we use the recurrence relation of memoization approach as dp(j) = min{dp(i) + abs(arr[i] – arr[j])} where i is in [0, N-1] and j is in [i + 1, j + K + 1], and K is number of jumps allowed.

Algorithm:

1. Create a dp[]  of size N and Initialize with a maximum value of Integer
2. Set dp[0]=0
3. We iterate the arr array, now for each index i we have K choices, and in the inner loop for each index j :
• dp[j] = min(dp[i] + abs(arr[i] – arr[j]),dp[j])
4. Then return then dp[N-1], which has the minimum cost to reach the end of the array.