本文介绍一种时间复杂度为多项式级别的动态规划方法，用于将已排序的正数列表划分为 k 个大小相近、且组内标准差之和最小的子组，适用于价格聚类、负载均衡等场景。
本文介绍一种时间复杂度为多项式级别的动态规划方法，用于将已排序的正数列表划分为 k 个大小相近、且组内标准差之和最小的子组，适用于价格聚类、负载均衡等场景。
在实际业务中（如电商商品按价格分档、服务器请求按响应时间分桶），我们常需将 N 个正数值划分为 K 个“尽可能等长 + 组内差异最小”的簇。直觉上先排序再均分看似合理，但存在关键缺陷：当 N 无法被 K 整除时，部分组需含 ⌊N/K⌋ 个元素，其余含 ⌈N/K⌉ 个——而哪几组多放一个元素，会显著影响总标准差。暴力枚举所有分配方式是指数级复杂度（如 k=20 时达 O(2k)），不可行。
正确解法是自顶向下动态规划（Top-Down DP），核心思想如下：
- 设 m = ⌊N/K⌋，则每组大小必为 m 或 m+1；
- 定义状态 dp[i][j] 表示将前 i 个已排序元素划分为 j 组的最小总标准差平方和（用方差替代标准差可避免开方，提升数值稳定性与效率）；
- 状态转移：最后一组取 m 个或 m+1 个元素：
dp[i][j] = min( dp[i - m][j - 1] + variance(arr[i-m:i]), dp[i - m - 1][j - 1] + variance(arr[i-m-1:i]) ) - 使用记忆化递归实现，时间复杂度为 O(N·K)，空间复杂度 O(N·K)。
✅ 关键优势：
- 排序预处理（O(N log N)）后，DP 过程严格保证全局最优；
- 每组连续子数组（因已排序，最优解必为连续段——由凸性可证）；
- 支持回溯重构分组路径（如答案中链表结构所示）。
? 注意事项：
- 输入必须预先升序排序，否则连续段假设不成立；
- 若需最小化“标准差之和”而非“方差之和”，可在最后统一开方，但优化目标仍建议用方差（可导、无偏、计算稳定）；
- 实际实现中建议使用 functools.lru_cache 或二维数组缓存，并预计算所有子区间方差以避免重复计算（O(N²) 预处理，O(1) 查询）。
以下为简化版 Python 实现框架（含方差预计算）：
import math
from functools import lru_cache
def min_variance_partition(nums, k):
nums.sort()
n = len(nums)
m = n // k
# precompute variance for all [i:j] in O(n^2)
var = [[0.0] * (n + 1) for _ in range(n)]
for i in range(n):
s = ss = 0.0
for j in range(i, n):
s += nums[j]
ss += nums[j] * nums[j]
cnt = j - i + 1
var[i][j + 1] = ss / cnt - (s / cnt) ** 2 # population variance
@lru_cache(None)
def dp(i, j): # min total variance for nums[0:i] into j groups
if j == 0: return 0.0 if i == 0 else float('inf')
if i < j * m or i > j * (m + 1): return float('inf')
res = float('inf')
# last group size: m or m+1
for size in [m, m + 1]:
if i >= size:
prev = dp(i - size, j - 1)
if prev != float('inf'):
res = min(res, prev + var[i - size][i])
return res
total_var = dp(n, k)
# Backtrack to get actual groups (omitted for brevity; use parent pointers or recursion)
return total_var该方法兼顾理论最优性与工程可行性，是解决“等长约束下最小内聚分组”问题的标准范式。对于千万级数据，还可结合分块预聚合或近似 DP 进一步优化。
