Stock Liao information

— Basic knowledge of stocks|Introduction to basics of stocks|Stock learning|Basic knowledge of stocks
Mobile access:m.liaochihuo.com

leetcode486. Winner prediction (Python3, c++)

Release Time:2021-07-04 Topic:Imitate the predictive winner index formula Reading:19 Navigation:Stock Liao information > Game > leetcode486. Winner prediction (Python3, c++) phone-reading

Article Directory

leetcode486. Winner prediction method: dynamic programming ideas: Code: Python3: cpp: Results:

leetcode486. Winner prediction

h1>

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 the score from either end of the remaining array, and then player 1 takes,.... A player can only get one score at a time, and the score is no longer available after it is taken. The game ends when there are no points left to take. The player with the most total points wins.

Given an array of scores, predict whether player 1 will become the winner. You can assume that each player's gameplay will maximize his score.

Example 1:

Input: [1, 5, 2] Output: False Explanation: At the beginning, player 1 can choose from 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 has only 1 (or 2) to choose from. So, the final score of player 1 is 1 + 2 = 3, and player 2 is 5. Therefore, player 1 will never be the winner, and False is returned.

Example 2:

Input: [1, 5, 233, 7] Output: True Explanation: Player 1 chooses 1 at the beginning. Then player 2 must choose from 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 it returns True, which means that player 1 can be the winner.

Tip:

1

bool

: n

=

len

(nums

​​)

# dp[ i ][ j] means when the remaining nums is in the closed interval of [i,j ], the first move and the second move Get the maximum value of the difference of scores,

# Finally, we return dp[ 0 ][ n-1] >0. dp

=

[

[

0

for _

in

range

(n

)

]

for _

in

range

(n

)

]

for i

​​in

range

(n

)

: dp

[i

]

[i

]

= nums

​​[i

]

for i

​​in

range

(n

-

1

,

-

1

,

-

1

)

:

for j

in

range

(i

+

1

,n

)

:

# The state transition equation is dp[ i ][ j] = max(nums[ i ]-dp[ i+1 ][ j ],nums[ j ]-dp[ i ][ j-1 ]) dp

[i

]

[j

]

=

max

(nums

​​[i

]

-dp

[ i

+

1

]

[j

]

, nums

​​[j

]

-dp

[i

]

[j

-

1

]

)

return dp

[

0

]

[n

-

1

]

>=

0

cpp:

class

Solution

{

public

:

bool

PredictTheWinner

(vector

& nums

​​)

{

int n

= nums

​​.

size

(

)

;

// dp[ i ][ j] means the remaining nums is [i,j] When the interval is closed, the maximum value of the difference between the scores obtained by the first hand and the second hand,

// Finally, we return dp[ 0 ][ n-1] >0. vector

dp

(n

,vector

( n

,

0

)

)

;

for

(

int i

​​=

0

;i

​​=

0

;i

--

)

for

(

int j

= i

+

1

; j

=

0

;

}

}

;

Result:

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

Label group:[dp

Hot topic

Game recommend

Game Popular