algorithm - 在这种情况下如何找到最优策略？

Question

场景看起来像这样:给定一个由 1 和 2 组成的数组，我们想让它全为 1。有以下约束:

1. 在每一步中，2 中的一个可以与相邻的交换位置。

            1 2 1 2 1
            could be transformed to:
            2 1 1 2 1 
            in single step.
   

2. 如果边上出现一个2，可以一步分解成2个1。

            2 1 2 1
          1 1 1 2 1
          in single step
   

3. 如果两个 2 相邻，则它们可以分解为 1。

           1 2 2 1
           into
           1 *1 1 1 1* 1
           it costs us 2 steps.
   

所以问题是，给定 n 个步骤，我们能否将其全部合并？我不想要完整的答案，一些小的见解也可以。

Answer 1

这是一个建设性的解决方案。

引理:破坏多个 2 从来都不是最优的靠近边界(左右)。

证明:假设在最优解中我们已经打破了最左边的两个 2 s 靠近左边界，它们在数组中的位置是 x和 y (x <= y)。我们使用了 x + y + 2行动来阻止他们。但是如果我们只是将它们移动到相邻的图 block 中并执行第三种操作，我们只能实现 y - x + 1操作。所以以前的解决方案不是最优的。证明。

所以只有4种情况:

• 根本不要使用第二个操作(仅当 2 的数量为偶数时)。
• 仅在左边界使用第二个操作(仅当 2 为奇数时)。
• 仅在右边界使用第二个操作(仅当 2 为奇数时)。
• 在两个边界都使用第二个操作(仅当 2 的数量为偶数时)。

在上层流程之后我们有偶数个2 .所以只需将它们配对并通过第 3 次操作制动。

解的复杂度是O(n) ，因为我们有 O(n)输入数据是处理这个问题的最佳方式。

随时提出问题或代码。