对字符串中的相同字符进行分组的最低成本

Question

我陷入了一个问题中。整体的问题陈述是很大的。我已经解决了它的其他部分。完好无损。

假设一个字符串包含一些破折号(‘-’)和一些字符('A')。此外，我们还得到了将字符移动到其相邻位置的成本C。我们需要找到最小的成本，这样所有的'A‘字符都是分组的。

Example1: A-A--A-A，成本= 10

对所有‘A’进行分组的最低成本为: 80

Example2: AAAA-A，成本= 10

对所有‘A’进行分组的最低成本为: 60

Answer 1

提示：为了使成本尽可能低，可以保留中位数之一(第一个示例中为4个中的第二个或第三个，第二个示例中为5个中的第三个)。使用它，您可以计算O(n)形式的成本，其中n是字符串的长度或As的数量，无论您的输入格式是什么。

Answer 2

我不认为这个问题需要动态编程。你只需要将所有的A移向中值A，因为这是所有A之间的最小总距离。

只要确保不移动介质A即可。如果中间的A向右移动，则其左侧的每个A将不得不多移动一步，而其右侧的每个A将不得不少移动一步。这应该会抵消掉，但您已经添加了一个不需要的步骤。