3

Minimum Cost to Reach End

Difficulty: MEDIUM
Contributed By
Sounak Majumder
Avg. time to solve
25 min
Success Rate
65%

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.
Sample Input 1 :
1
5 3
1 3 4 5 2
Sample Output 1 :
3
Explanation to Sample Input 1 :
Since K = 3, 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-1)  i.e 2 and then we take a jump of 3 from 1st index to the last index with the cost of abs(2-3). I.e 1 Therefore the minimum cost to reach the end of the array is (2+1) i.e 3
Sample Input 2 :
1
7 3
20 30 40 25 15 20 28
Sample Output 2 :
8
Explanation to Sample Input 2 :
Since K = 3, the optimal way to reach the end of the array with minimum cost is to take a jump to 3rd index from 0th index with the cost of abs(25-20)  i.e 5 and again we take a jump of 3 from 3rd index to the last index with the cost of abs(28-25). I.e 3 Therefore the minimum cost to reach the end of the array is (5+3) i.e 8.
Reset Code
Full screen
copy-code
Console