Stock Liao information

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

Leetcode: NO.486 Winner prediction depth first + dynamic programming

Release Time:2021-07-04 Topic:Imitate the predictive winner index formula Reading:19 Navigation:Stock Liao information > Game > Leetcode: NO.486 Winner prediction depth first + dynamic programming phone-reading

Question

Given an array of non-negative integers representing scores. 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, the player

1 can start from

1 and

2 to choose from. If he chooses

2 (or

1 ), then the player

2 can start from

1 (or

2) and

5. If the player

2 selects

5, then the player

1 will only be left with

1 (or

2) Optional. Therefore, the final score of player

1 is

1

+

2

=

3, and the player

2 is

5. Therefore, the player

1 will never be the winner and returns False. Example

2: Input:

[

1

,

5

,

233

,

7

] Output: True Explanation: Player

1 at the beginning Select

1. Then the player

2 must choose from

5 and

7. No matter which player

2 chooses, player

1 can choose

233. In the end, the player

1 (

234 points) gets more points than the player

2 (

12 points), so Return True, indicating that the player

1 can be the winner. Tip:

1

int n

= nums

​​.length

; span> step

=

new

int

[n

]

[n

]

;

this

.nums

= nums

​​;

for

(

int

[

] ints

: step

)

{ Arrays

.

fill

(ints

, Integer

.MIN _ VALUE

)

;

}

return

dfs

(

0

, n

-

1

)

>=

0

;

}

private

int dfs

(

int left

,

int right

)

{

if

(left

> right

)

return

0

;

if

(step

[left

]

[right

]

!= Integer

.MIN _ VALUE

)

return step

[left

]

[right

]

; span>

int leftScore

= nums

​​[left

]

-

dfs

(left

+

1

, right

)

;

int rightScore

= nums

​​[right

]

-

dfs

(left

, right

-

1

)

;

int score

= Math

.

max

(leftScore

, rightScore

)

; step

[left

]

[right

]

= score

;

return score

;

}

}

Recursion is thinking right, and the machine is moving backwardsPlanning is thinking backwards, the machine is doing it

/** * @author: ffzs * @Date: 2020/9/1 8:37 AM */

public

class

Solution2

{

public

boolean

PredictTheWinner

(

int

[

] nums

​​)

{

int n

= nums

​​.length

;

int

[

]

[

] dp

=

new

int

[n

]

[n

]

;

// Fill in the dividing line first

for

(

int i

​​=

0

; i

​​=

0

; i

--

)

{

for

(

int j

= i

+

1

; j

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

Label group:[dynamic programming

Hot topic

Game recommend

Game Popular