marcog的解决方案是解决该问题的正确，非递归的多项式时间解决方案-这是一个非常标准的DP问题-
但是，为了完整起见，这里提供了一个可行的证明以及该问题的实际代码。[@marcog：如果愿意，可以将此答案的任何部分复制到您自己的文件中；然后，我将其删除。]

证明

让列表为x 1，…，X ñ。假设wlog该列表已排序。我们正在尝试从列表中找到K个（不相交的）元素对，以使它们之差的总和最小化。

索赔 ：最佳解决方案始终由连续元素的差异组成。
证明
：假设您修复已采取差异的元素的子集。然后根据JonasKölker给出的证明_，仅此子集_
的最佳解决方案包括列表中连续元素的差异。现在假设有一个对应于不包含成对连续元素的子集的解决方案，即该解决方案涉及一个差x j -x i，其中j> i +
1。然后，我们可以替换x Ĵ为x I + 1得到一个更小的区别，因为
X 我 ≤X I + 1 ≤X Ĵ⇒X i + 1的 -x 我 ≤X Ĵ -x 我。
（不用说，如果x i + 1 = x j，则采用x i + 1与采用x j是没有区别的。）这证明了这一主张。

剩下的只是常规的动态编程内容：使用前n个元素中的k个对的最优解根本不使用第n个元素（在这种情况下，它只是使用前n-1个中的k对的最优解），
或者 它使用第n个元素，在这种情况下，它是差x n -x n-1加上使用前n-2个对的k-1对的最优解。

正如marcog所说，整个程序的运行时间为O（N log N + NK）。（排序+ DP。）

码

这是一个完整的程序。我懒于初始化数组，并使用字典编写了Python代码。与使用实际数组相比，这是一个很小的log（N）因子。

'''
The minimum possible sum|x_i - x_j| using K pairs (2K numbers) from N numbers
'''
import sys
def ints(): return [int(s) for s in sys.stdin.readline().split()]

N, K = ints()
num = sorted(ints())

best = {} #best[(k,n)] = minimum sum using k pairs out of 0 to n
def b(k,n):
    if best.has_key((k,n)): return best[(k,n)]
    if k==0: return 0
    return float('inf')

for n in range(1,N):
    for k in range(1,K+1):
        best[(k,n)] = min([b(k,n-1),                      #Not using num[n]
                           b(k-1,n-2) + num[n]-num[n-1]]) #Using num[n]

print best[(K,N-1)]

测试一下：

Input
4 2
1515 1520 1500 1535
Output
30

Input
8 3
1731 1572 2041 1561 1682 1572 1609 1731
Output
48