1872. Stone game VIII describes the derivation in detail

1872. Stone game VIII

There are many good explanations on the official website of this problem. Here I introduce the process from the original solution step by step to the optimization of O(n)O(n)O(n). You can also view it as the transfer equation

[I] f = Max (f [I + 1], the pre – f [I] [I + 1]) f [I] = Max (f [I + 1], the pre – f [I] [I + 1]) f [I] = Max (f [I + 1], the pre – f [I] [I + 1]) of a supplement

The key step is to find the key word “prefix and”.

In general, the pebble series can “draw” a tree to see how it works from top to bottom. But if we were to draw directly from the original input here, we would get something like this. Input: featuring = [- 1, 2, 3, 4 -, – 5] stones = [1, 2, 3, 4, 5] stones = [- 1, 2, 3, 4 -, – 5).

The figure above is the result of iterating through each round of choices. Where, the square represents Alice’s turn to choose, and the circle represents Bob’s turn to choose. However, notice that Both Alice and Bob want to make the best choice for themselves. Suppose the final choice is A1+A2+… + Ax – (B1, B2 and… By)A_1 + A_2 + … + A_x – (B_1 + B_2 + … B_y)A1+A2+… + Ax – (B1, B2 and… By). So when Alice face input [- 1, 2, 3, 4 -, 5] – [1, 2, 3, 4, 5] [- 1, 2, 3, 4 -, – 5], from the picture above shows that he has a total of four choices, and in the end he sure is a choice:

Similarly, when It’s Bob’s turn to choose, he’s going to choose minminmin to get the best result.

// It is -(-2) because Bob’s number, discussed above, acts as a subtraction in the final result

Obviously, this is a recursive problem. Each problem needs to be solved based on the results of the subproblems, so it makes intuitive sense to take a bottom-up approach, and of course bottom-up recursion can be optimized by mnemonizing recursion. From the above analysis, it is easy to see that one of the variables in the subproblem is whether the current turn is chosen by Alice or Bob. If it’s Alice, it’s plus her choice 0 and otherwise it’s minus her choice. To indicate whether Alice or Bob can use a variable turnturnturn. When turn=0turn =0turn =0, it means Alice’s turn in the current turn. Turn = 1Turn =1turn =1 indicates Bob’s turn. But the difficulty is what’s a good choice for the other variable? Each subproblem is an array, although you can see from the tree above that there are many duplicate inputs, but how to express an array of inputs ？？？？？

Here’s the answer: it’s back to prefix and. As you can see from the observation, both Alice and Bob. The numbers I pick are actually prefixes and sums. So let’s figure out the prefix sum first. You can then draw the following selection tree

So another factor in the dimension of the problem comes into play, which is the prefix and the array subscript!

Method 1: the most consistent with the top-down thinking + memory

 // Go straight to Stack Overflow
    public int stoneGameVIII(int[] stones) {
        int[] prefixSum = new int[stones.length];
        prefixSum[0] = stones[0];

        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + stones[i];
        }

        Integer[][] mem = new Integer[stones.length + 1] [2];

        mem[stones.length - 1] [0] = prefixSum[stones.length - 1];
        mem[stones.length - 1] [1] = -prefixSum[stones.length - 1];
        Arrays.fill(mem[stones.length], 0);

        return solve(prefixSum, mem, 1.0);
    }

    private int solve(int[] prefixSum, Integer[][] mem, int start, int turn) {
        if(mem[start][turn] ! =null) {
            return mem[start][turn];
        }

        int result = turn == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        for (int i = start; i < prefixSum.length; i++) {
            if (turn == 0) {
                result = Math.max(result, prefixSum[i] + solve(prefixSum, mem, i + 1.1));
            } else {
                result = Math.min(result, -prefixSum[i] + solve(prefixSum, mem, i + 1.0));
            }
        }

        mem[start][turn] = result;
        return result;
    }
Copy the code

Note: the start argument indicates the number from which the currently selected person starts, and the turn argument indicates whose turn it is. 0 is Alice, 1 is Bob. Solve (prefixSum, MEM,1,0)solve(prefixSum, MEM,1,0)

The above code is more in line with human thinking, making choices from top to bottom. But unfortunately StackOverflow error…

Method 2: backward-to-front iterative method + memorized search

 public int stoneGameVIII(int[] stones) {
        int[] prefixSum = new int[stones.length];
        prefixSum[0] = stones[0];

        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + stones[i];
        }

        Integer[][] mem = new Integer[stones.length + 1] [2];

        mem[stones.length - 1] [0] = prefixSum[stones.length - 1];
        mem[stones.length - 1] [1] = -prefixSum[stones.length - 1];
        Arrays.fill(mem[stones.length], 0);


        for (int i = stones.length - 2; i >= 1; i--) {
            int zeroResult = Integer.MIN_VALUE, oneResult = Integer.MAX_VALUE;
            for (int j = i; j < stones.length; j++) {
                zeroResult = Math.max(zeroResult, prefixSum[j] + mem[j + 1] [1]);
                oneResult = Math.min(oneResult, -prefixSum[j] + mem[j + 1] [0]);
            }
            mem[i][0] = zeroResult;
            mem[i][1] = oneResult;
        }

        return mem[1] [0];
    }
Copy the code

Method two is an improvement on method one. Unfortunately, it’s obviously order n2 O n squared O n2. So I’m out of time.

Method 3: Optimize nested loops

Observe the calculation process of MEM [I][0] MEm [I][0] MEm [I][0]

Mem [I +1][0] MEm [I +1][0] MEm [I +1][0] MEm [I +1][0]

Mem [I][0]mem[I][0]mem[I]

​
$mem[i][0] = max(prefixSum[i] + mem[i + 1][1], mem[i + 1][0] )$

And the combination of the above equation, can launch mem [I] [0] = – mem [I] [1] mem [I] [0] = – mem [I] [1] mem [I] [0] = – mem [I] [1]

Thus, the above equation can be reduced to:

Mem [I] [0] = Max (prefixSum [I] – mem [0], [I + 1] mem [I + 1] [0]) mem [I] [0] = Max (prefixSum [I] – mem [0], [I + 1] Mem mem [I + 1] [0]) [I] [0] = Max (prefixSum [I] – mem [0], [I + 1] mem [I + 1] [0])

As you can see, the second dimension indicating whether the current turn is Alice’s or Bob’s turn can be removed. The final result is the transfer equation given on the official website:

​

Mem [I] = Max (prefixSum [I] – mem [I + 1], the mem) [I + 1] mem [I] = Max (prefixSum [I] – mem [I + 1), Mem mem [I + 1]) [I] = Max (prefixSum [I] – mem [I + 1], the mem/I + 1)

At this point, the derivation is complete!

See the code:

 public int stoneGameVIII(int[] stones) {
        int[] prefixSum = new int[stones.length];
        prefixSum[0] = stones[0];

        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + stones[i];
        }

        Integer[][] mem = new Integer[stones.length + 1] [2];

        mem[stones.length - 1] [0] = prefixSum[stones.length - 1];
        mem[stones.length - 1] [1] = -prefixSum[stones.length - 1];
        Arrays.fill(mem[stones.length], 0);


        for (int i = stones.length - 2; i >= 1; i--) {
            int zeroResult = Integer.MIN_VALUE, oneResult = Integer.MAX_VALUE;

            zeroResult = Math.max(prefixSum[i] + mem[i + 1] [1], mem[i + 1] [0]);
            oneResult = Math.min(-prefixSum[i] + mem[i + 1] [0], mem[i + 1] [1]);

            mem[i][0] = zeroResult;
            mem[i][1] = oneResult;
        }

        return mem[1] [0];
    }
Copy the code

Method 4: one-dimensional transfer equation

 public int stoneGameVIII(int[] stones) {
        int[] prefixSum = new int[stones.length];
        prefixSum[0] = stones[0];

        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + stones[i];
        }
        Integer[] mem = new Integer[stones.length + 1];

        mem[stones.length - 1] = prefixSum[stones.length - 1];

        for (int i = stones.length - 2; i >= 1; i--) {
            mem[i] = Math.max(prefixSum[i] - mem[i + 1], mem[i + 1]);
        }
        return mem[1];
    }
Copy the code