Can anyone help me with this problem?

Given n integers and a number k (k<=n/2). Find the smallest sum of the absolute differences of k pairs of an array.

Example 1:

Input:

5 2

2 5 3 3 6

Output:

1

Explain: |3 - 3| |6 - 5| = 1

Example 2:

Input:

6 3

868 504 178 490 361 603

Output:

462

Explain: |868 - 603| |504 - 490| |178 - 361| = 462

I had tried brute force but can't pass other testcases with large number. I think this could be solved with dynamic programming but don't know how to do it.

This is my code: https://pastecode.io/s/o124xi0q

CodePudding user response：

Assuming O(N * K) solution would pass, then we can solve the problem using dynamic programming.

Let dp[i][j] be the minimun cost to use the first sorted i numbers, using j pairs. We can write:

dp[0][j] = INT_MAX; // for each j between 0 and K.
dp[i][j] = std::min(dp[i - 1][j], a[i] - a[i - 1]   dp[i - 2][j - 1]); // for each j between 0 and i / 2