algorithm - 使用不断变化的数组

这是一个递归解决方案，但我不知道它是否是最优的：

从数组中最小的数字开始。在示例[1 1 1 2 1]中，为1。原因是合并其他元素后不会得到新的1。所以它们很容易使用。

显然，如果您有偶数个连续的 1，则将它们全部合并绝不是次优的。因此，我们需要决定如何处理奇数个连续元素。其中一个需要省略（不合并），一旦我们选择了那个，其余部分都有偶数个 1。

这里重要的观察是，一旦你选择了要遗漏的元素，它左边的数组和它右边的数组就构成了两个独立的问题。由于中间会有一个 1，因此不能将右侧的任何数字与左侧的任何数字合并。因此，对于每一个可能的选择，您可以递归地解决右子数组和左子数组的问题，然后找到最小结果。

算法

总结该方法，这些是要遵循的步骤：

如果数组的长度为 0，则返回 0。
找到数组中的最小元素。称它为 x。
再检查一次数组，创建一个新数组，其中偶数个连续的 x 都被合并。
如果您在数组中的任意位置看到奇数个 x，请执行以下操作：
- 设第一个元素的索引为 i。对于每个属于 x 序列的 j = i, i+2, i+4, ...，解决子数组 [0 .. j-1] 和 [j+1 .. end] 的问题。称他们的结果为 n1 和 n2。
- 从这些可能的拆分中返回最小值 n1 + n2 + 1。
如果您没有看到奇数个 x，那么数组中就没有 x。回到步骤 1。

请注意，您可以在第 4 步中将 x 替换为 x+1，并相应地选择子问题索引，以可能在递归调用中节省一些工作。

代码

这是一个执行此操作的 c++ 代码：

#include <iostream>
#include <limits>
#include <vector>

// the range is [start, end)
int
solve(std::vector<int>& array, int start, int end)
{
    if (start >= end)
        return 0;

    int length = end - start;

    // find the minimum element
    int min = array[start];
    for (int i = start; i < end; i++)
        if (array[i] < min)
            min = array[i];

    std::vector<int> newArray;
    newArray.reserve(length + 1);
    int minCount = 0; // number of consecutive elements that are equal to min
    int firstOddNumber =
      -1; // index of an odd number of consecutive min's in the new array
    int oddNumbers = 0; // number of min's starting at firstOddNumber

    for (int i = start; i <= end; i++) {
        // iterate one last time with i == end to run the checks again.
        // hence the special case. we pop this element after the loop.
        int elem = i < end ? array[i] : min + 1;

        if (elem == min) {
            minCount++;
        } else if (minCount != 0) {
            // even number of min's
            if (minCount % 2 == 0) {
                // merge them
                for (int j = 0; j < minCount / 2; j++)
                    newArray.push_back(min + 1);
            } else {
                // do not merge them but save their index in the new array
                firstOddNumber = newArray.size();
                oddNumbers = minCount;
                for (int j = 0; j < minCount; j++)
                    newArray.push_back(min);

                // ^^^ this part could be modified as I wrote in the note in my
                // answer
            }
            minCount = 0;
            newArray.push_back(elem);
        } else
            newArray.push_back(elem);
    }

    // remove the min+1 element pushed when i == end
    newArray.pop_back();

    if (firstOddNumber == -1)
        // no odd number of consecutive min's, repeat the procedure
        return solve(newArray, 0, newArray.size());
    else {
        int minResult = newArray.size();
        // solve two subproblems for each possible split
        for (int i = firstOddNumber; i <= firstOddNumber + oddNumbers; i += 2) {
            int result = 1 + solve(newArray, 0, i) +
                         solve(newArray, i + 1, newArray.size());
            if (result < minResult)
                minResult = result;

            // ^^^ this part could be modified as I wrote in the note in my
            // answer
        }
        return minResult;
    }
}

void
test(std::vector<int> v, int expected)
{
    int result = solve(v, 0, v.size());
    std::cout << result << '\n';
    if (result == expected)
        std::cout << "CORRECT\n" << std::endl;
    else
        std::cout << "EXPECTED: " << expected << '\n' << std::endl;
}

int
main()
{
    test({ 1, 1, 1, 2, 1 }, 3);
    test({ 1, 1, 1, 1, 1 }, 2);
    test({ 1, 1, 1, 1, 1, 1 }, 2);
    test({ 1, 2, 1, 1, 1 }, 3);
    test({ 1, 2, 1, 2, 1 }, 5);
}

algorithm - 使用不断变化的数组

问题描述

解决方案

算法

代码

推荐阅读