arrays - 将数组分为 k 个或更少的子部分，以最小化每个部分的最大总和

Question

我需要将一个数组分成 k 个或更少的子部分，以最小化每个部分的最大总和。

例如，数组包含元素:5,10,21,20

如果k=2，数组可以分为2个子数组:{5,10,21}和{20}。我们必须返回子数组的最大和(上例中的36)。

当k>=4时，答案将是数组中最大的元素。

此外，数组元素的选择顺序无法更改，因此我们不能只对数组进行排序并继续。

Answer 1

这显然是一个动态规划问题。

数组除法的问题就相当于在数组中进行k-1次除法。

让你的数组被称为A。设 m[i,k] 为 A 中元素的最佳划分，直到第 i 个元素为止 k 个划分

m[0,*] = 0
m[i,0] = a[i] 
m[i,j] = min{m[i-1,j] + a[i], max{m[i-1,j-1], a[i]}}

m[i,j]是在i点处分割数组与不分割之间的最小值。

计算一下就能找到答案

m[length(A), k-1]

您可以从那里回溯划分。