求移除k个连续元素消除数组的最小插入次数算法

问题描述 #

给定一个长度为n的数组和数值k，目标是找到最少插入次数，满足以下规则：

• 可插入任意数值的元素
• 当连续相同元素的数量≥k时，可选择移除这组连续元素
• 移除后，前后的元素会拼接在一起，可继续进行移除操作
• 最终需要完全消除整个数组，可选择最优的移除时机

输入格式 #

• 第一行：空格分隔的n和k
• 第二行：数组元素
• 第三行：预期输出

测试用例 #

Test Case 1 #

2 5
1 1
3

解释：插入3个1，形成5个连续1后移除，总插入次数为3。

Test Case 2 #

5 3
2 2 3 2 2
2

解释：最优方案是在中间的3后插入2个3，先移除这组3（共3个），剩余的4个2自动连续，可直接移除，总插入次数为2。若先处理2的话需要插入4个元素，成本更高。

Test Case 3 #

10 4
3 3 3 3 2 3 1 1 1 3
4

解释：插入3个元素（2个2、1个1）消除中间的2和1段，剩余的3会拼接成连续的组，可自动移除，总插入次数为4。

我的尝试 #

我尝试过用贪心栈的方法，但没有成功，目前找不到可行的解题思路。作为DSA新手，希望能得到这个问题的可行算法思路或者相关的解题方向指导。

内容的提问来源于stack exchange，提问作者Ragul Shanmugarajan