Nuggets team number online, help you Offer impromptu! Click for details
Given an array of non-negative integers representing fractions. Player 1 takes a score from either end of the array, then Player 2 continues to take a score from either end of the remaining array, then Player 1 takes… . A player can only take one score at a time, and the score is no longer valid once taken. The game ends when no remaining points are available. The player with the most total points wins.
Given an array representing scores, predict whether player 1 will be the winner. You can assume that each player’s play will maximize his score.
Example 1:
Input: [1, 5, 2] Output: False Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose between 1 (or 2) and 5. If player 2 chooses 5, then player 1 is left with 1 (or 2) to choose from. So, player 1’s final score is 1 + 2 = 3, while Player 2 is 5. Therefore, player 1 is never the winner and returns False.
Example 2:
Input: [1, 5, 233, 7] Output: True Explanation: Player 1 initially chooses 1. Player 2 then has to choose between 5 and 7. No matter which player 2 chooses, player 1 can choose 233. In the end, Player 1 (234 points) gets more points than Player 2 (12 points), so returning True means player 1 can be the winner.
Their thinking
Dp [I][j]= math.max (nums[I]-dp[I]-dp[I +1][j],nums[j]-dp[I][I][J-1]). Take first hand from left 2. Take first hand from right
code
class Solution {
public boolean PredictTheWinner(int[] nums) {
int n=nums.length;
int[][] dp=new int[n][n];
for(int i=n-2; i>=0; i--)for(int j=i+1; j<n; j++) dp[i][j]= Math.max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
return dp[0][n-1] > =0; }}Copy the code