algorithm - 按顺序划分数组

Question

这是我一个 friend 的面试题，我想不出怎么解。

问题:

给定一个包含 n 个红色或蓝色按钮的数组。存在 k 个容器。容器的值(value)由其中存在的红色按钮和蓝色按钮的乘积给出。问题是将按钮放入容器中，使容器中所有值的总和最小。此外，所有容器都必须包含按钮，并且必须按给定的顺序放置。例如，第一个按钮只能转到第一个容器，第二个按钮可以转到第一个或第二个但不能转到第三个(否则第二个容器将没有任何按钮)。k 将小于或等于 n。

我认为这必须有一个动态规划解决方案。

你如何解决这个问题？到目前为止，我只有微不足道的情况

• 如果 (n==k)，答案将为零，因为您可以在每个容器中放一个，使每个容器的值为零，因此总和将为零。
• 如果 (k==1)，您只需将它们全部转储并计算乘积。
• 如果只有一种颜色，答案将为零。

编辑:

我举个例子。

n = 4 和 k = 2

输入:R B R R

第一个容器获得前两个(R 和 B)使其值为 1(1R X 1B)第二个容器获得剩余的(R 和 R)使其值为 0(2R x 0B)答案是 1 + 0 = 1

如果k=3，第一个容器只有第一个按钮 (R)第二个容器只有第二个(B)第三个将有最后两个按钮(R 和 R)每个容器的值为 0，因此总和和答案将为 0。

希望这能消除疑虑。

Answer 1

可能的 DP 解决方案:

让dp[i, j] = minimum number possible if we put the first i numbers into j containers .

dp[i, j] = min{dp[p, j - 1] + numRed[p+1, i]*numBlues[p+1, i]}, p = 1 to i - 1

答案将在 dp[n, k] 中.

int blue = 0, red = 0;
for (int i = 1; i <= n; ++i)
{
    if (buttons[i] == 1)
        ++red;
    else
        ++blue;

    dp[i][1] = red * blue;
}

for (int i = 2; i <= n; ++i)
    for (int j = 2; j <= k; ++j)
    {
        dp[i][j] = inf;

        for (int p = 1; p <= i; ++p)
            dp[i][j] = min(dp[p][j - 1] + getProd(p + 1, i), dp[i][j]);
    }

return dp[n][k];

复杂度将为 O(n^3*k) , 但可以减少到 O(n^2*k)通过制作getProd运行 O(1)在某些预计算的帮助下(提示:使用 dp[i][1] )。如果在那之前没有人发现这实际上是错误的，我会在明天发布。

也有可能减少到 O(n*k) ，但这可能需要不同的方法......