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

The title

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.

Tip:

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

Their thinking

To define an array

Dp [I][j] represents the difference in score between the first and last players for the subarray [I…j]

State transition

For dp[I][j], assume that the first player is A and the second player is B

  • The difference between player B’s score and player A’s score after the piles were picked up by player A first is called DP [I +1][J]
  • The difference between player B’s score and player A’s score after the piles were picked up by player A is called DP [I][J-1]

Choose the situation with more points

code

class Solution {
    public boolean stoneGame(int[] piles) {

        int n=piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i]=piles[i];
        }
        for (int i=n-2; i>=0; i--) {for (int j=i+1; j<n; j++) dp[i][j]= Math.max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1]);
        }
        return dp[0][n-1] >0; }}Copy the code