Classic interval DP & classic game

This is the 16th day of my participation in Gwen Challenge

Topic describes

This is the 877. Pebble game on LeetCode, medium difficulty.

Tag: interval DP, Game Theory

Alex and Li are playing with piles of stones. An even number of piles were laid out in a row, with positive integer stones in each pile.

The game is decided by who has the most stones in his hand. We have an odd number of pebbles, so there’s no draw.

Alex and Li took turns. Alex started first. Each turn, the player takes the entire stack of stones from the beginning or end of the row. This continues until there are no more pebbles, at which point the player with the most pebbles wins.

Assuming alex and Lee both play their best, return true when Alex wins the match and false when Lee wins the match.

Example:

Input: [5,3,4,5] Output: true Explanation: Alex starts first and can only take the first or last five stones. Let's say he takes the first five, the row becomes [3,4,5]. If lee takes the first 3, then the rest is [4,5], and alex takes the last 5 to win 10 points. If lee takes the last 5, then the rest is [3,4], and alex takes the last 4 to win 9 points. This indicates that taking the first five stones was a winning move for Alex, so we return true.Copy the code

Tip:

• 2 <= piles.length <= 500
• Piles. Length is even.
• 1 <= piles[i] <= 500
• Sum piles is odd.

Dynamic programming

define
$f[l][r]$Is considered as the interval
$[l,r]$, what is the maximum point difference between the first hand and the second hand when both sides make the best choice.

Then f[1][n] F [1][n]f[1][n] is the score difference between the first hand and the last hand considering all stones:

• 
  $f[1][n] > 0$, the first hand will win, returnTrue
• 
  $f[1][n] < 0$, the first hand will be defeated, returnFalse

Without loss of generality consider how f[l][r]f[l][r]f[l][r] how to transfer. Pilespilespiles can only be taken from both ends. There are two cases:

• Piles were collected from the left end of the piles, and the values of piles were [L −1]piles[L −1]; After taking the stones, the original cause is a solution, from [m + 1, r] [m + 1, r] [m + 1, r] interval make the optimal decision, the value of f [m + 1] [r] f [m + 1] [r] f [m + 1] [r]. Therefore, if we take stones from the left endpoint first, the difference between the two sides is:

• Read [R −1]piles[R −1] from the right end; After taking the stones, the original cause is a solution, from [l, r – 1] [l, r – 1] [l, r – 1] interval make the optimal decision, the value of f – 1 [r] [l] f [l] [r – 1] f [l] [r – 1]. Therefore, if the pebble is taken from the right endpoint first, the difference between the two sides is:

Both sides want to win and make the best decision (even if they have the biggest margin). So f[l][r]f[l][r]f[l][r] is the maximum of the two cases.

According to the state transition equation, we find that the state value of the large interval depends on the state value of the cell, which is a typical interval DP problem.

It can be solved according to the conventional practice of “enumerating interval length” and “left endpoint of interval” from small to large.

Code:

class Solution {
    public boolean stoneGame(int[] ps) {
        int n = ps.length;
        int[][] f = new int[n + 2][n + 2]; 
        for (int len = 1; len <= n; len++) { // Enumerate the length of the interval
            for (int l = 1; l + len - 1 <= n; l++) { // enumerate the left endpoint
                int r = l + len - 1; // Compute the right endpoint
                int a = ps[l - 1] - f[l + 1][r];
                int b = ps[r - 1] - f[l][r - 1]; f[l][r] = Math.max(a, b); }}return f[1][n] > 0; }}Copy the code

• O(n2)O(n^2)O(n2)
• Space complexity: O(n2)O(n^2)O(n2)

Game theory

In fact, this is a classic game theory problem, the simplest kind of game theory problem.

For convenience, we call the “stone sequence” the number of stones in the original order, with subscripts starting at 111.

Because we have an even number of pebbles, and we can only take pebbles from both ends. Therefore, the sequence of stones that can be selected by the first hand and the second hand completely depends on each decision of the first hand.

Since the number of stones is even, the first hand can “freely” choose the odd or even sequence for each decision situation, thus limiting the second hand to “only” odd or even stones next time.

Specifically, in this case, because the number of pebbles is even, the initial situation of the first hand must be [odd, even][odd, even][odd, even], that is, it must be “the situation with different parity”; When the first hand finishes the decision, the hand handed to the second hand is either [odd, odd][odd, odd][odd, odd] or [even, even][even, even], that is, it must be “the situation with the same parity”. After the decision is made by the latter hand, the “parity situation” is restored and handed back to the first hand…

It is not hard to generalize that this boundary can be applied to every turn.

Therefore, the first hand only needs to calculate which of the “odd sum” and “even sum” in the original sequence is larger before the first operation, and then “restrict” the other party to choose only the opposite of the “optimal parity sequence” in each decision.

At the same time, because the sum of all stones is odd, the pile number is even, that is, there is no tie, so the first hand will win.

Code:

class Solution {
    public boolean stoneGame(int[] piles) {
        return true; }}Copy the code

• Time complexity: O(1)O(1)O(1)
• Space complexity: O(1)O(1)O(1)

The last

This is the No.877 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks, we will first finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.