Link to the original question:

For this question, you can use

recursion and

dynamic return in the solution Two ideas are solved, and the one chosen here is realized by moving back.

The first thing to note is that in the problem, it is assumed that each player's gameplay will maximize his score, and player 1 is the first mover.

**public boolean PredictTheWinner(**

**int[] nums) {****int[ ][] dp =****new****int[ nums.length ][ nums.length ]; dp[ dp.length-****1 ][ dp.length-****1] = nums [nums.length-****1 ];****for (****int****left = dp.length-****2;****left >=****0;****left--) {****for (****int****right =****left;****right** right++) { **if (**

**left ==****right) {dp[****left ][****right] = nums[****left ];}****else {****int pickLeft = nums[****left]-dp[****left +****1 ][****right ];****int pickRight = nums[****right]-dp[****left ][****right-****1 ]; dp[****left ][****right] = Math.max(pickLeft, pickRight);}}} return dp[****0 ][ nums.length-****1] >=****0;}**The sum of the scores obtained by both parties is certain. The dynamic programming algorithm here considers twoThe difference of the person. In other words, the sum of the points scored by player 1 minus the sum of points scored by player 2 will win if it is greater than 0 in the end.

The above is the AC algorithm. For the auxiliary array dp[ left ][ right ], there is a transfer equation:

dp[**left ][****right] = max(****nums[ left]-dp[ left + 1 ][ right ], nums[ right]-dp[ left ][ right-1 ])**this It means that player 1 and player 2 are in the interval [left, right ], the difference between the total score of player 1 and the total score of player 2. Among them, the value of dp[ left ][ right] is dynamically dependent on dp[ left + 1 ][ right] and dp[ left ][ right-1 ]. The specific relationship is as above. If player 1 chooses the leftmost score at this time , Player 2 can only dynamically choose from the leftmost + 1 to the rightmost interval. At this time, Player 2 will also choose the best answer according to the remaining interval; when Player 1 chooses the rightmost score, it is also in this way.

When player 1 chooses the leftmost score, there are nums[ left]-dp[ left + 1 ][ right ], which means that player 1 chooses the leftmost score nums[ left ], and then subtract Go to

** the difference between the best choice obtained by player 2 in the remaining interval [left-1 ][ right] and the total score of player 1** dp[ left + 1 ][ right ], this is the player 1 and player 2 are in the interval [left, right ]. The difference between the two is the total score difference. Among them, the subtracted dp[ left + 1 ][ right] (or dp[ left ][ right-1]) dynamically represents the difference between player 1 and player 2 which are mutually exclusive.

Regarding the above paragraph, you may have doubts. Here is a specific example to explain:

** For the array {1,2,3}, there are:** p> dp[

**1,3] = max(1-dp[**

**2 ][****3 ], 3-dp[****1 ][****2 ])dp[****2,3] = max(3-dp[****2 ][****2 ], 2-dp[****3 ][****3 ])****= max(3-2, 2-3)****= 3-2dp[****1,2] = max(1-dp[****2 ][****2 ], 2 -dp[****1 ][****1 ])****= max(1-2, 2-1)****= 2-1then dp[ 1,3] = max(1-(3-2), 3-(2-1))****= max(1-3 + 2, 3-2 + 1)**** 1-(3-2) further becomes 1-3 + 2 where the numbers 1 and 2 corresponding to the positive sign are **

** Player 1**The number 3 corresponding to the negative sign is the choice of

** Player 2**, and the result of 1-3 + 2 is the difference between the total score of player 1 minus the total score of player 2, and you need to pay attention to max(1-dp[ 2 ][ 2 ], 2-dp[ 1 ][ 1 ]) where dp[ 2 ][ 2] represents in the partial interval {2} of the overall array {1,2,3} The difference between the total score of player 2 minus the total score of player 1, because after player 1 chooses 1 in the partial interval {1,2} in the overall array {1,2,3}, player 2 has only 2 to choose from Now,

** dp[ 2 ][ 2] is for player 2 at this time. **

But if the entire array has only {1,2}, then dp[ 2 ][ 2] is for player 1.

Article Url:https://www.liaochihuo.com/info/596402.html

Label group:[dp]