Dynamic Programming Practice 2


Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Assembly, Awk, Brain****, C, C++, Java, Pascal, Perl, Python, Sed, Text

Mike starts at stone \(1\) and wishes to reach stone \(N\). Mike can jump up to \(K\) stones forward. Each stone \(i\) has a height \(h_{i}\). The cost for jumping between stones \(i\) and \(j\) is \(|h_{i} - h_{j}|\). Help Mike find the minimum cost needed to reach stone \(N\).

Constraints

\(1 \leq N \leq 10^{4}\)

\(1 \leq K \leq 100\)

\(1 \leq h_{i} \leq 10^{3}\)

Input Specification

The first line contains two integers, \(N\) and \(K\).

The second line contains \(N\) integers, \(h_{i}\).

Output Specification

Output one integer, the minimum cost.

Sample Input

5 3
1 3 4 5 2

Sample Output

3

Explaination for Sample Output

The optimal path is through stones \(1\), \(2\), and \(5\). This incurs a cost of \(|h_1 - h_2| + |h_2 - h_5| = |1 - 3| + |3 - 2| = 2 + 1 = 3\). It can be shown that a lower cost is impossible.


Comments

There are no comments at the moment.