如何从n个正整数中选P个独立对使两两绝对差之和最小

前置步骤：数组排序 #

你的初始思路方向完全正确，第一步必须先对数组做升序排序。这里可以先证明一个核心结论：排序后的最优解中，所有配对的元素一定是相邻的。
假设有四个升序排列的数a ≤ b ≤ c ≤ d，如果选择非相邻配对(a,c)和(b,d)，总和为(c-a)+(d-b) = (d-a)+(c-b)；如果选择相邻配对(a,b)和(c,d)，总和为(b-a)+(d-c)，显然后者远小于前者。跨元素配对只会带来更大的差值总和，因此排序后只需要考虑相邻元素的配对组合即可。

动态规划求解 #

状态定义 #

定义dp[i][j]为：从前i个排序后的元素中，选出j个无重叠的独立对，能得到的最小绝对差总和。这里下标采用1-based计数，方便边界处理。

边界条件 #

• 当j=0时，选0个配对的总和恒为0，即dp[i][0] = 0对所有i ≥ 0成立
• 当i < 2*j时，元素数量不足以选出j个配对，该状态值设为无穷大（表示不可达）

递推公式 #

对于第i个元素，我们只有两种选择：

1. 不将第i个元素纳入任何配对：此时最小和等于前i-1个元素选j个配对的最小和，即dp[i-1][j]
2. 将第i个元素和第i-1个元素配对：此时消耗了两个元素，最小和等于前i-2个元素选j-1个配对的最小和，加上当前相邻元素的差值，即dp[i-2][j-1] + arr[i-1] - arr[i-2]（排序后无需取绝对值）
   因此最终递推公式为：
   dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + arr[i-1] - arr[i-2])

复杂度说明 #

• 时间复杂度：O(n log n + n*P)，其中O(n log n)是排序的开销
• 空间复杂度：常规实现为O(n*P)，可以通过滚动数组优化到O(P)

示例代码（Python） #

def min_pair_sum(arr, p):
    arr.sort()
    n = len(arr)
    # 滚动数组优化空间，只保留前两次的状态
    prev_prev = [float('inf')] * (p + 1)
    prev_prev[0] = 0
    prev = [float('inf')] * (p + 1)
    prev[0] = 0
    
    for i in range(2, n + 1):
        curr = [float('inf')] * (p + 1)
        curr[0] = 0
        max_j = min(p, i // 2)
        for j in range(1, max_j + 1):
            curr[j] = min(prev[j], prev_prev[j-1] + arr[i-1] - arr[i-2])
        prev_prev, prev = prev, curr
    return prev[p]

# 测试示例
print(min_pair_sum([1,2,3,4,5,6,7], 2)) # 输出2，符合预期

内容的提问来源于stack exchange，提问作者Akash Kumar