对于这个问题有O(n^2)方法吗？

Question

给定N个元素的数组，我需要将其拆分为k个子数组，其中k可以介于2 <= k <= N之间。子数组的得分取决于：

(左边界点-子数组的右边界点)^2+max(子数组)。

如果这有意义的话，左侧边界点将是元素的索引，右边边界点将是(元素+1的索引)。您可以将它们看作是拆分数组的点。

在O(n^2)中找到一个算法，该算法计算所有子数组的分数之和，以便它是可能得到的最低分数。

例如：

数组= 5,3,4,9,2,8

子阵列= 5,3，4,9,2，8

第一个子数组的得分= (2-0)^2 + (5) =9

第二个子阵列的得分= (5-2)^2 + (9) = 18

第三个子阵列的得分= (6-5)^2 + (8) =9

所有子数组的所有分数之和= 36。

我想做的是：

我尝试选择数组的分区，这样：(子数组的左边界点-右边界点)^2

但我不知道这样做是否正确。谢谢!

Answer 1

动态编程可以在O(N^2)中做到这一点。因为这可能是家庭作业，我不会给你代码。

我将从一个更简单的问题开始，即如何为1 <= k <= N解决这个问题。

与往常一样，动态编程可以自上而下或自下而上地进行。通常，递归比自上而下的回忆录更容易实现。但是在这种情况下，你的分数函数更容易自下而上。

我们要做的是，通过开始长度，得到一系列最好的解决方案。起始数组是[5,3,4,9,2,8]。我们首先：

best = []

接下来，我们想知道以下几点：

score of [5] = (5-5)**2 + 5 = 5

所以我们得到：

best = [5]

接下来，我们要附加以下内容：

best[0] + score of [3] = 5 + (3-3)**2 + 3 = 8
score of [5, 3] = (5-3)**2 + 5 = 9

所以我们得到：

best = [5, 8]

接下来，我们要附加以下内容：

best[1] + score of [4] = 8 + (4-4)**2 + 4 = 12
best[0] + score of [3, 4] = 5 + (3-4)**2 + 4 = 10
score of [5, 3, 4] = (4-5)**2 + 5 = 6

所以我们得到：

best = [5, 8, 6]

等等，直到我们得到：

best = [5, 8, 6, 15, 15, 16]

但有个问题。这16项是最低限度的：

best[4] + score of [8]
best[3] + score of [2, 8]
best[2] + score of [9, 2, 8]
best[1] + score of [4, 9, 2, 8]
best[0] + score of [3, 4, 9, 2, 8]
score of [5, 3, 4, 9, 2, 8]

最后一个条目是k=1的解决方案。因此，您必须正确地重新计算最后一分钟，以确定答案。(在本例中，这是答案，因为16对应于拆分的[5, 3, 4], [9, 2, 8]，但您必须检查。)

如果您以最简单的方式实现这一点，您将得到一个O(n^3)算法，因为这些score of ...操作需要计算一个子列表，查看它的端点，并找到最大值。有O(n^2)这样的计算，找到子列表和最大值可能是O(n)。但是，如果您稍微聪明地保持运行最大值的总数，而不是每次实际生成这些子列表，那么您就可以进入O(n^2)了。