首先，一维案例。给定一个包含 N 个数字的数组，将其分成 n 个块，以使每个元素与其块平均值的平方距离之和最小化。例如，如果要求将 [0.1,0.3,2,1.2,1.3] 分成三部分，则最优解是 [[0.1,0.3],[2],[1.2,1.3]]。
使用动态编程，这可以在 O(N * n) 中轻松解决
现在是 2D 案例。给定一个 (N,M) 矩阵，我们想将它切成 n*m 块。解决方案应该看起来像一个不规则间隔的网格 - 它是一组 n 个水平切口和 m 个垂直切口。
这似乎更棘手。可以通过固定水平切割来动态找到最佳垂直切割，但这似乎并没有导致任何地方。枚举所有可能的水平切割 O(C(M,m)) 是棘手的。
有没有办法在多项式时间内做到这一点？