算法动态规划

Question

您将看到一个由数字组成的数组(数组大小为10^5)，您需要将该数组划分为K个分区(k<=500)，以便每个分区的最小元素之和为最大

假设数组包含a1，a2，a3.......现在f(x) = min(a1，a2..ax) + min(a(x+1)，a(x+2)...ay) +..........a(z+1)....a(n)

现在f(x)应该是最大值

其中分区必须是连续的。

所需的复杂性。(n*k)

我简单地逐个固定最大元素，并尝试看看它是否可以划分为K分区，如果可以，我计算了f(x)

Answer 1

当分区数为i时设为dp[i] = f(x)，其中f(x)由OP定义，现在开始求解--基本情况--

dp[n]=sum(array elements);
//ie when number of partitions is n we return sum of elements as each element is in different partition

现在,

dp[i-1] = dp[i] - min of partition collapsed in this step

因此，现在我们只需找到需要在每个步骤中折叠的分区。这可以通过暴力一次获取两个相邻的分区并保留最不利于分区崩溃的标签(可以在O(N)中完成)来完成。

因此，总体时间复杂度为O(n*n-k)，空间复杂度为O(n)。好吧，这是技能的限制，任何人谁可以帮助提高欢迎。