如何重排整数数组以最小化相邻元素乘积之和？

给定一个包含n个整数的数组arr，需要对其进行重排，最小化线性相邻元素的乘积之和，即计算：
sum(arr[i] * arr[i+1] for i in range(n-1))

示例 #

示例1 #

• 输入：n=7，arr=[1,10,2,7,10,6,6]
• 最优排列：[10,1,7,6,6,2,10]
• 最小结果：127

示例2 #

• 输入：arr=[2,4,10,9,3]
• 最优排列：[10,2,4,3,9]
• 最小结果：67

已尝试方法的局限性 #

之前尝试的贪心策略都存在普适性问题：

• 简单贪心：排序后将最小与最大元素配对，这种逻辑在示例2中失效——最大数10并不适合直接和最小数2相邻，反而放在两端搭配更小的中间元素能得到更优结果。
• 改进贪心：将最大数放在一端、第二大数放在最小数旁的启发式规则，依然无法覆盖所有场景，尤其是数组包含负数时，正负元素的组合逻辑会更复杂，贪心很难做出正确选择。

最优解法：动态规划 #

贪心无法解决所有情况，而动态规划可以通过枚举所有可能的最优子结构，得到全局最优解。

核心思路 #

1. 先排序数组：将数组按升序排列，这样我们可以通过从两端选取元素来构建最优序列（排序后，最优排列必然是从两端依次取元素的组合，这是该问题的核心性质）。
2. 定义DP状态：
   • dp[i][j][0]：使用了排序后数组中索引i到j的所有元素，且当前序列的最后一个元素是arr[i]时的最小乘积和。
   • dp[i][j][1]：使用了排序后数组中索引i到j的所有元素，且当前序列的最后一个元素是arr[j]时的最小乘积和。
3. 状态转移：
   处理区间[i,j]时，只能从更小区间[i+1,j]或[i,j-1]转移而来：
   • 若最后一个元素是arr[i]，前一个元素只能是arr[i+1]或arr[j]，取两者的最小乘积和：
     dp[i][j][0] = min(dp[i+1][j][0] + arr[i]*arr[i+1], dp[i+1][j][1] + arr[i]*arr[j])
   • 若最后一个元素是arr[j]，前一个元素只能是arr[i]或arr[j-1]，取两者的最小乘积和：
     dp[i][j][1] = min(dp[i][j-1][0] + arr[j]*arr[i], dp[i][j-1][1] + arr[j]*arr[j-1])
4. 初始状态：当区间长度为1时（i==j），没有相邻元素，乘积和为0，即dp[i][i][0] = dp[i][i][1] = 0。
5. 最终结果：处理完整个数组后，取dp[0][n-1][0]和dp[0][n-1][1]中的较小值。

代码实现（Python） #

def min_adjacent_product_sum(arr):
    n = len(arr)
    if n <= 1:
        return 0
    arr.sort()
    # 初始化DP表：dp[i][j][0]对应最后元素为arr[i]，dp[i][j][1]对应最后元素为arr[j]
    dp = [[[0]*2 for _ in range(n)] for __ in range(n)]
    
    # 单个元素的情况，乘积和为0
    for i in range(n):
        dp[i][i][0] = dp[i][i][1] = 0
    
    # 按区间长度从小到大填充DP表
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 计算dp[i][j][0]
            option1 = dp[i+1][j][0] + arr[i] * arr[i+1]
            option2 = dp[i+1][j][1] + arr[i] * arr[j]
            dp[i][j][0] = min(option1, option2)
            
            # 计算dp[i][j][1]
            option3 = dp[i][j-1][0] + arr[j] * arr[i]
            option4 = dp[i][j-1][1] + arr[j] * arr[j-1]
            dp[i][j][1] = min(option3, option4)
    
    return min(dp[0][n-1][0], dp[0][n-1][1])

验证与扩展 #

• 运行示例1：输入[1,10,2,7,10,6,6]，代码返回127，与示例结果一致。
• 运行示例2：输入[2,4,10,9,3]，代码返回67，与示例结果一致。
• 处理负数：比如输入[-5, -3, 2, 4]，代码会计算出最小乘积和为-38，对应最优排列[-5,4,-3,2]，符合预期。

内容的提问来源于stack exchange，提问作者Bharat Reddy