以下是 LeetCode 3801. 合并有序列表的最小成本 的 Python3 实现方法签名为 def minMergeCost(self, lists: List[List[int]]) - int。核心思路- 关键观察任意子集合并后的有序列表其中位数只取决于该子集包含哪些原始列表与合并顺序无关。- Meet-in-the-Middle 状态压缩 DP1. 将 n ≤ 12 个列表平分为前后两半分别预处理所有子集合并后的有序数组。2. 对任意 mask利用「两个有序数组的中位数」算法LeetCode 4 变体在 O(log L) 内求出中位数。3. 子集 DPdp[mask] 表示将 mask 对应列表合并为一个的最小成本。枚举所有非空真子集转移。- 复杂度时间 O(2^n · L 3^n)空间 O(2^n L)其中 L ≤ 2000 为总长度。pythonfrom typing import Listclass Solution:def minMergeCost(self, lists: List[List[int]]) - int:n len(lists)def merge(a: List[int], b: List[int]) - List[int]:合并两个有序数组i j 0res []while i len(a) and j len(b):if a[i] b[j]:res.append(a[i])i 1else:res.append(b[j])j 1if i len(a):res.extend(a[i:])if j len(b):res.extend(b[j:])return resdef calc_sorted(sub_lists: List[List[int]]) - List[List[int]]:预计算 sub_lists 所有子集合并后的有序数组m len(sub_lists)u 1 msorted_arr [[] for _ in range(u)]for i in range(m):high_bit 1 ifor s in range(high_bit):sorted_arr[high_bit | s] merge(sub_lists[i], sorted_arr[s])return sorted_arrdef find_median_sorted_arrays(a: List[int], b: List[int]) - int:找两个有序数组合并后的下中位数。偶数长度时取左侧中间元素题目定义。if len(a) len(b):a, b b, am, n_len len(a), len(b)left, right 0, mwhile left right:mid (left right) // 2j (m n_len 1) // 2 - mid - 2if j 1 n_len and a[mid] b[j 1]:right midelse:left mid 1i left - 1j (m n_len 1) // 2 - i - 2if i 0:return b[j]if j 0:return a[i]return max(a[i], b[j])# 1. 分治预处理前后两半的所有子集合并结果m n // 2sorted1 calc_sorted(lists[:m])sorted2 calc_sorted(lists[m:])u 1 nhalf (1 m) - 1# 2. 预计算每个 mask 的中位数和总长度median [0] * ufor mask in range(1, u):median[mask] find_median_sorted_arrays(sorted1[mask half],sorted2[mask m])# 3. 子集 DPINF float(inf)dp [0] * ufor mask in range(u):if mask (mask - 1) 0: # 0 或单个列表无需合并continuedp[mask] INFsub (mask - 1) mask# 只枚举 sub other 避免重复计算对称性while sub (mask ^ sub):other mask ^ subdp[mask] min(dp[mask],dp[sub] dp[other] abs(median[sub] - median[other]))sub (sub - 1) mask# 加上当前合并的长度成本len(sub) len(other) len(mask)dp[mask] len(sorted1[mask half]) len(sorted2[mask m])return dp[u - 1]验证结果输入 期望 实际[[1,3,5],[2,4],[6,7,8]] 18 18[[1,1,5],[1,4,7,8]] 10 10[[1],[3]] 4 4[[1],[1]] 2 2