Leetcode -877- Stone game

[Blog link]

A path to learning at 🐔

The nuggets home page

[B].

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. Suppose Alex and Lee both play their best and alex returns when he wins the matchtrueCome back when Lee wins the racefalse. Example: Enter: [5.3.4.5] output:trueExplanation: Alex starts first, can only take the first5Or after5Stone. Let's say he took the first5Star, this row becomes [3.4.5]. If Lee takes away before3Student: So what's left is4.5] after Alex took it5A win10Points. If Lee takes it away5Student: So what's left is3.4] after Alex took it4A win9Points. This shows that before taking5The stone was a winning move for Alex, so we turned backtrue. Tip:2 <= piles.length <= 500Piles. Length is even.1 <= piles[i] <= 500Sum piles is odd. Related Topics minimization maximum mathematical dynamic programming 👍277 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Mathematics-game theory

  • The even-length array always gets larger elements at both ends, so the first hand always wins
public boolean stoneGame(int[] piles) {
            return true;
        }
Copy the code

Time complexity O(1)

Idea 2: Dynamic planning

  • One subproblem to consider is to first read Math.max(Piles [0], Pilse [1]) when the element array has only two elements
  • Recursively expand both sides of the interval [0, j + 1]
  • The range of the interval can be expanded regardless of whether the first hand and the second hand obtain the maximum value of the current interval endpoint
  • Use l and r to represent the left and right boundaries if you first pick the left end element of the interval inside [L,r]
  • The first piles are piles[L-1], the second piles are piles[L +1], the right piles are piles[R]]
  • First hand piles are piles[R-1] and second hand piles are piles Max[L],piles[R-1]]
  • The first hand will take precedence over the one that gets the maximum difference and let’s assume that a is the first hand element and B is the last one
  • Math.max[(a1-b1),(a2-b2)]
  • A1a2 b1b2 represent elements from both sides and Julio cruz scores and scores of corresponding to a subsequent party if according to the recursive thinking can be simply defined a recursive function int (int l, int r, int [] piles)
  • Represents the maximum difference of score obtained when the current L and r are the boundary and the observed variable parameters are L and r
  • So you can define a dp[n+1][n+1]
  • N is for piles length indicates the maximum difference between the first and second hands obtained when left and right boundaries are Ij, ensuring the highest score for each first hand
  • dp[i][j] = Math.max(a, b)
 public boolean stoneGame(int[] piles) {
            int n = piles.length;
            int[][] dp = new int[n + 1][n + 1];
            //
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    int a = piles[i] - dp[i + 1][j];
                    int b = piles[j] - dp[i][j - 1]; dp[i][j] = Math.max(a,b); }}return dp[0][n-1] > 0;
        }
Copy the code

Time complexity O(
n 2 n^2 )