数组无序度问题的动态规划递归解法：寻找最小总无序度排列

问题定义 #

给定由n个正整数组成的序列a=(a₁,a₂,…,aₙ)：

• 前k项子序列的无序度D(aₖ)为该子序列最大值与最小值的差值
• 总无序度为k从2到n时所有D(aₖ)的总和
• 目标：找到排列b*使总无序度最小，并给出动态规划递归解法

关键前置结论 #

已证：最优排列b*的最后一个元素必为原序列的最大值或最小值，基于此可构建动态规划模型。

动态规划方案 #

预处理 #

先将原序列排序，得到sorted_a = [s₁, s₂, ..., sₙ]，满足s₁ ≤ s₂ ≤ ... ≤ sₙ。排序后可直接追踪子序列的最小、最大值。

状态定义 #

定义dp[i][j]为使用排序后序列中第i到第j个元素（即sᵢ到sⱼ）构成的子排列的最小总无序度（对应k从2到j-i+1的D(aₖ)之和）。

递归状态转移 #

对于长度l = j-i+1 ≥ 2的子序列：

• 若在i到j-1的最优子排列末尾添加sⱼ（当前最大值），新增的无序度为sⱼ - sᵢ（前l项的最大最小差值）
• 若在i+1到j的最优子排列末尾添加sᵢ（当前最小值），新增的无序度同样为sⱼ - sᵢ

因此递归转移方程为：

dp(i, j) = min(dp(i, j-1), dp(i+1, j)) + (sorted_a[j] - sorted_a[i])

边界条件 #

• 当i == j时，子序列长度为1，总无序度为0（无k≥2的项）
• 当j = i+1时，子序列长度为2，总无序度为sorted_a[j] - sorted_a[i]（仅k=2时的一项）

递归实现代码示例 #

def min_total_disorder(sorted_a, i, j, memo):
    if i == j:
        return 0
    if j == i + 1:
        return sorted_a[j] - sorted_a[i]
    if (i, j) in memo:
        return memo[(i, j)]
    
    val = min(
        min_total_disorder(sorted_a, i, j-1, memo),
        min_total_disorder(sorted_a, i+1, j, memo)
    ) + (sorted_a[j] - sorted_a[i])
    memo[(i, j)] = val
    return val

最优排列构造 #

在递归计算过程中记录每一步的选择（添加最大值或最小值），回溯即可得到最优排列：

1. 从dp[0][n-1]开始，若该值由dp[0][n-2] + (sorted_a[-1]-sorted_a[0])得到，说明最后添加的是最大值，递归构造0到n-2的最优排列后将最大值放在末尾
2. 若该值由dp[1][n-1] + (sorted_a[-1]-sorted_a[0])得到，说明最后添加的是最小值，递归构造1到n-1的最优排列后将最小值放在末尾
3. 对中间子问题重复上述逻辑，直到得到完整排列

示例验证 #

以示例a=(6,2,3,1,3,3)为例：

• 排序后sorted_a=[1,2,3,3,3,6]
• 递归计算得dp[0][5] = 8，与示例总无序度一致
• 回溯得到最优排列[3,3,3,2,1,6]

以示例a=(1,3,3,3,6,6)为例：

• 排序后sorted_a=[1,3,3,3,6,6]
• 递归计算得dp[0][5] = 11，与示例总无序度一致
• 回溯得到最优排列[3,3,3,6,6,1]

内容的提问来源于stack exchange，提问作者Lefteris Galatas