Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

sample

Topic describes

LeetCode 1140. Stone Game II

Alex and Li continued their stone game. Piles of stones were laid out in a row, each with integer positive stones. The game is decided by who has the most stones in his hand.

Alex and Li took turns. Alex started first. Initially, M is equal to 1.

In each player’s turn, that player can take all the remaining stones from the first X heap, where 1 <= X <= 2M. And then, let’s say M = Max (M, X).

The game continues until all the stones have been removed.

Assuming alex and Lee both play their best, return the maximum number of stones alex can get.

Example:

Input: haemi = [2,7,9,4,4] output: 10 interpretation: if alex had taken a pile of stones at the beginning, lee had taken two piles and then alex had taken two piles. In this case, Alex gets 2 + 4 + 4 = 10 stones. If Alex takes two piles of pebbles at the beginning, then Lee can take all three. In this case, Alex gets 2 + 7 = 9 stones. So let's return a bigger 10.Copy the code

Data range

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4

Their thinking

This is a game problem, but it’s also a dynamic programming problem. Dynamic programming generally requires two steps:

  1. State (subproblem) definition
  2. State transition equation

The more difficult ones are usually the transfer equations, which take into account forward/reverse transfer order, boundaries, etc. But if you use mnemonic search, you don’t need to worry about that at all.

To return to this problem, let’s define the state first: dp[I][j] is the maximum number of stones left by the person who took the first stack of stones when M=j. So our initial problem is to find dp[0][1].

How to calculate dp[I][J]?

First of all, if 2j is greater than the number of pebbles left, we can take away all of the pebbles.

Otherwise, the number of pebbles we can take is 1-2J. Enumerates the number of pebbles taken by player A at this time X, where 1<=X<= 2J, then when it is player B’s turn to take, PLAYER B can take dp[I +X][Max (j, X)] at most. If we know that the total number of pebbles is set to total before A picks up pebbles, then we subtract the number of pebbles B takes away, which is the number of pebbles A can get if A picks up pebbles X, total-dp [I +X][Max (j, X)].

Prefix [n] = prefix[n] = prefix[n] = prefix[n] = prefix[I] = prefix[I] = prefix[I] = prefix[I] = prefix[I] = prefix[I] The remaining number of pebbles is naturally prefix[n] -prefix [I].

AC code (annotated in detail)

/ * * *@param {number[]} piles
 * @return {number}* /
var stoneGameII = function(piles) {
    let n = piles.length; // Total n pebbles

    // Preprocess the prefix and
    let prefix = new Array(n + 1).fill(0); // prefix[I] indicates the sum of the prefixes of the preceding I numbers
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + piles[i];
    }
    // Store the result to initialize dp[n+1][n+1] with all values -1
    let dp = new Array(n + 1).fill().map(() = > new Array(n + 1).fill(-1));
    // The maximum number of pieces that can be taken by the first player with m=j
    function dfs(i, j) {
        // Use dp to store the calculation result
        if(dp[i][j] ! = = -1) {
            return dp[i][j];
        }
        // The current total number of pebbles
        let total = prefix[n] - prefix[i];
        // If the remaining heap can be taken away, it will be taken away directly
        if (n - i <= 2 * j) {
            return dp[i][j] = total;
        }
        // Otherwise enumerate the number of pebbles taken away
        let answer = 0;
        for (let x = 1; x <= 2 * j; x++) {
            // Calculate the maximum number of pebbles the other person can get
            let other_max = dfs(i + x, Math.max(x, j));
            // The current user can get all the pebbles - the number of pebbles the other person can get
            answer = Math.max(answer, total - other_max);
        }
        // Returns the result and stores it to dp
        return dp[i][j] = answer;
    }

    return dfs(0.1);
};
Copy the code

As can be seen, with mnemonic search, there is no need to consider the order of calculating subproblems, only need to use DFS () to obtain the required state, the key is to need to store the results after each calculation, because a subproblem may be calculated several times, otherwise it will time out.

If you understand this, you can look at this problem 1510. Stone game IV, similar idea, but simpler, one-dimensional dp can be solved.

Tip: dp[I] indicates whether the player wins first hand when there are I stones left, and then enumerates the number of stones taken by the current player each time.