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

Question

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

在每一步中，2的其中之一可以与相邻的交换位置。

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

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

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

如果两个二相邻，它们可以分解成一个。

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

那么问题来了，给定n个步骤，我们能把它全部变成一个吗？我不想要完整的答案，一些小见识也可以。

Answer 1

我尝试开发 动态规划 算法但找不到 最优子结构。

这是暴力，最耗时，递归解决方案。

我们必须找出是否可以将输入减少到全 1。输入数组有 1 和 2，并且有将 2 转换为 1 的规则。

天真的做法是尽可能应用规则并尝试找出是否可以实现输出

伪码-ey算法为：

boolean check(int[] input, int steps) {
    if(steps == 0) {
        return allOnes(input)
    }
    step--
    boolean ans = false;

    if(input[0] == 2) {
        breakEdgeTwoIntoOne(input,0) // function for rule 2
        revert(input) // convert input to original 
        ans = ans | check(input,steps)
    }

    if(input[input.length-1] == 2) {
        breakEdgeTwoIntoOne(input,input.length - 1)
        revert(input)
        ans = ans | check(input,steps)
    }

    for(i=0;i<input.length-1;i++) {
        if(input[i] == 2 && input[i+1] == 2) {
            breakTowAdjecentTwosIntoOnes(input,i) // function for rule 3
            revert(input)
            ans = ans | check(input,steps)
        }
    }

    for(i=0;i<input.length-1;i++) {
        if( input[i] == 2 ) {
            swapLeft(input, i) // function for rule 1
            ans = ans | check(input,steps)
            revert(input)
            swapRight(input, i)
            ans = ans | check(input,steps)
            revert(input)
        }
    }

    return ans;
}

所有功能的不那么 elegnet java 实现：

static boolean check(int[] input, int steps) {
    if (allOnes(input)) {
        return true;
    }
    if (steps == 0) {
        return allOnes(input);
    }
    steps--;
    int original[] = new int[input.length];
    System.arraycopy(input, 0, original, 0, input.length);
    boolean ans = false;
    if (input[0] == 2) {
        ans = ans | check(breakEdgeTwoIntoOne(input, 0), steps);
        System.arraycopy(original, 0, input, 0, input.length);
    }

    if (input[input.length - 1] == 2) {
        ans = ans | check(breakEdgeTwoIntoOne(input, input.length - 1), steps);
        System.arraycopy(original, 0, input, 0, input.length);
    }

    for (int i = 0; i < input.length - 1; i++) {
        if (input[i] == 2 && input[i + 1] == 2) {
            ans = ans | check(breakTowAdjecentTwosIntoOnes(input, i), steps);
            System.arraycopy(original, 0, input, 0, input.length);
        }
    }
    for (int i = 0; i < input.length - 1; i++) {
        if (input[i] == 2) {
            if (i != 0) {
                ans = ans | check(swapTwoToLeft(input, i), steps);
                System.arraycopy(original, 0, input, 0, input.length);
            }
            if (i != input.length - 1) {
                ans = ans | check(swapTwoToRight(input, i), steps);
                System.arraycopy(original, 0, input, 0, input.length);
            }
        }
    }
    return ans;
}

private static int[] breakTowAdjecentTwosIntoOnes(int[] input, int i) {
    int op[] = new int[input.length + 2];
    int k = 0;
    for (int j = 0; j < input.length; j++) {
        if (j == i || j == i + 1) {
            op[k++] = 1;
            op[k++] = 1;
            // j++;
        } else {
            op[k++] = input[j];
        }
    }
    return op;
}

private static int[] breakEdgeTwoIntoOne(int[] input, int i) {
    int op[] = new int[input.length + 1];
    if (i == 0) {
        op[0] = 1;
        op[1] = 1;
        System.arraycopy(input, 1, op, 2, input.length - 1);
    } else {
        op[op.length - 2] = 1;
        op[op.length - 1] = 1;
        System.arraycopy(input, 0, op, 0, input.length - 1);
    }
    return op;

}

private static int[] swapTwoToRight(int[] input, int i) {
    if (i != input.length - 1) {
        int k = input[i + 1];
        input[i + 1] = input[i];
        input[i] = k;
    }
    return input;
}

private static int[] swapTwoToLeft(int[] input, int i) {
    if (i != 0) {
        int k = input[i - 1];
        input[i - 1] = input[i];
        input[i] = k;
    }
    return input;
}

private static boolean allOnes(int[] input) {
    for (int x : input) {
        if (x != 1)
            return false;
    }
    return true;
}

部分测试用例

[1,2,1,2,1],1 => false
[1,2,1,2,1],2 => true
[1,2,1,2,1],3 => true

[2,2,2],1 => false
[2,2,2],2 => true
[2,2,2],3 => true
[2,2,2],4 => true

Answer 2

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

引理： 在边界附近（左右）打破一个以上 2 从来都不是最佳选择。

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

所以只有 4 种情况：

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

经过上层处理后我们有偶数个2。所以只需将它们配对并通过第 3 次操作制动。

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

随时提问或代码。

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

How to find the optimal strategy in this scenario?

algorithm

mathematical-optimization