algorithm - 需要删除创建的重复项的算法

Question

我有一个程序需要编写，但我不确定如何编写。我需要引用如何解决它的方法。问题如下:
您有一个包含 N 个整数的列表。例如:[4;2;3;2;1;5;1;3;2]。
如果有一些 K 或更多的相邻重复数字，它们将被从列表中删除。您可以在任何两个数字之间添加任何数字，或者添加到列表的开头/结尾，以便从列表中删除这些数字。

任务是使用尽可能少的数字清除列表。

1 <= N <= 100 - N 是列表的长度。
2 <= K <= 5 - K 是从序列中删除的重复相邻数字的最小数量。

K 在指定范围内提供。

例子:List = [4;2;3;2;1;5;1;3;2] - 答案是3； K = 2

我的想法是拥有某种序列树，以便有效地删除数字。这个例子的树看起来像:

4 2       2
   3     3
    2 1 1
       5

所以你必须在列表的第 4 和第 5 个元素之间添加 5(从 0 开始)，然后第 4 到第 7 个元素消失，序列看起来像这样。

4 2   2
   3 3
    2

现在您在新序列的第 2 和第 3 个元素之间添加 2，因此第 1 到第 5 个元素被删除。

然后你将 4 添加到一个新序列中，则添加到序列中的数字总数为 3。这个问题的算法是什么？谢谢。

Answer 1

让我们对问题进行逆向工程。考虑到您的示例，可以减少的最终字符串将如下所示

4           4
 2         2
  3       3
   2     2
    1   1
     5 5

如果您注意到它是一个长度均匀的回文。对于所有其他可能的输入，情况也是如此。

现在问题可以简化为找到输入中最长的回文子序列，并向输入字符串中添加一个字符，该字符对应于输入中不在回文子序列中的每个字符。寻找最长回文子序列是一个标准的 DP 问题，可以找到教程 here

例如，在您的情况下，最长的子序列是 [2,3,1,1,3,2] 而不在输入中的字符是 [4,2 ,5] 所以你必须将这些添加到输入中，或者如果你对数字感兴趣，那么 3 将是答案。