我正在阅读此http://www.cas.mcmaster.ca/~terlaky/4-6TD3/slides/DP/DP.pdf并想知道是否存在对分区问题具有更好时间复杂度的解决方案。
从链接:
“假设给定一个非负数 {s1,...,sn} 和整数 k 的排列 S。如何将S 分成 k 个或更少的范围,以最小化所有范围内的最大和?
例如
S = 1,2,3,4,5,6,7,8,9
k=3
通过将 S 切割成这 3 个范围,最大范围 (8,9) 的总和为 17,这是可能的最小值。
1,2,3,4,5|6,7|8,9
链接中建议的算法在 O(kn^2) 中运行并使用 O(kn) 空间。有没有更高效的算法?