私はこの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) スペースを使用します。より効率的なアルゴリズムはありますか?