按顺序对数组进行分区

Question

这是一个我的朋友得到的面试问题,我无法想出如何解决它.

题:

您将获得一组n个按钮,分别为红色或蓝色.有k个容器.容器的值由红色按钮和蓝色按钮的产品给出.问题是将按钮放入容器中,使得容器的所有值的总和最小.此外,所有容器必须包含按钮,并且必须按顺序放置它们.例如,第一个按钮只能转到第一个容器,第二个按钮可以转到第一个或第二个而不是第三个(否则第二个容器将没有任何按钮).k小于或等于n.

我认为必须有一个动态的编程解决方案.

你是如何解决这个问题的？到目前为止,我只得到了琐碎的案例

• 如果(n == k),答案将为零,因为您可以在每个容器中放置一个使每个容器的值为零,因此总和将为零.
• 如果(k == 1),您只需转储所有这些并计算产品.
• 如果只有一种颜色,则答案为零.

编辑:

我举个例子.

n = 4且k = 2

输入:RBRR

第一个容器得到前两个(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

如果我正确理解问题的话，只要每个容器中至少有一个按钮，您就可以选择任何容器来放置剩余的按钮。鉴于此，在每个容器中放置一个按钮，确保至少有一个带有红色按钮的容器和至少一个带有蓝色按钮的容器。然后将剩下的按钮，将所有红色按钮放入一个有红色按钮的容器中，将所有蓝色按钮放入一个有蓝色按钮的容器中。这将使每个容器至少有一个按钮，并且每个容器只有一种颜色的按钮。那么每个容器的分数都是 0。因此总和是 0 并且您已经最小化了组合分数。