Stock Liao information

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

LeetCode 486. Winner prediction (memorized search / dynamic programming)

Release Time:2021-07-04 Topic:Predicting winners prediction point formula Reading:19 Navigation:Stock Liao information > Game > LeetCode 486. Winner prediction (memorized search / dynamic programming) phone-reading

LeetCode link

LeetCode 486

ps: I recently found that memoized search is really easy to use~~

1. Problem description

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:

Example 2:

Second, problem analysis and code

When I first saw the question, I thought it was against 877 . The stone game is similar. Don’t feel too cool to solve the problem ingeniously. The problem is also from the left and right of the array, and the final value is the largest to win, but it has different qualifications:

The length of the array is an even number, the array The sum of the values ​​is an odd number. When encountering this problem, there is always the urge to solve violently. However, when the upper bound of the array length is 500, we give up the idea directly, but when we calm down and think about the given conditions, we try to simulate it. During the process, you will find that the first hand has the advantage. He can control the opponent to only take the value under the even or odd index. In other words, the first hand only needs to calculate the largest sum of the even number and the odd index. Principle), if you get the value directly according to the index's parity, you will definitely win, so the question directly

return True.

1. Memoized search

Back to the topic, obviously this question does not have such strong qualifications, because it is difficult for us to judge when the number of arrays is odd. However, if we take a closer look at the upper bound of the array length as 20, we can happily return to the search method. After saving the sub-problem of repeated calculation, the problem is solved.

Because it takes left and right, you need the left and right boundaries of the array. Use dic to save the maximum score that player 1 can get under the interval [left, right ]. The recursive function dfs(nums, left, right) is just like this The maximum score that the interval can get.

Code (Python)

class

Solution

:

def

PredictTheWinner

(self

, nums

​​: List

[

int

]

)

-

>

bool

: n

=

len

(nums

​​) total

=

sum

(nums

​​) dic

=

{

}

def

dfs

(nums

​​, left

, right

)

:

if left

>right

:

return

0

if

(left

, right

)

in dic

:

return dic

[

(left

, right

)

] curSum

=

sum span>

(nums

​​[left

:right

+

1

]

) best

=

max

(curSum

-dfs

( nums

​​, left

+

1

, right

)

, curSum

-dfs

(nums

​​, left

, right

-

1

)

)

# The process of the game, in two situations, make player 1 and player 2 the best dic

[

(left

, right

)

]

= best

return best player1

= dfs

(nums

​​,

0

, n

-

1

)

return player1

>=total

-player1

2 . Dynamic programming

We can also use dynamic programming to solve this problem. Use dp[ i, j] to indicate that when the remaining number is nums[ i… j ], the current player (note that it is not necessarily the first mover) and the other player's maximum score difference. The current player can choose nums[ i] and leave nums[ i+1… j ], or choose nums[ j] and leave nums[ i… j-1 ], so the state transition equation is:

dp [i ][ j] = max(nums[ i ]-dp[ i+1 ][ j ], nums[ j ]-dp[ i ][ j-1 ])

dp[ i ][ i] = nums[ i ]

Code (Python)

class

Solution

(

object

)

:

def

PredictTheWinner

(self

, nums

​​)

: n

=

len

(nums

​​) dp

=

[

[

0

for i

​​in

range

(n

)

]

for j

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

)

: dp

[i

]

[j

]

=

max

(nums

​​[i

]

-dp

[i

+

1

]

[ j

]

, nums

​​[j

]

-dp

[i

]

[j

-

1

]

)

return dp

[

0

]

[n

-

1

]

>=

0

Q: Why does i traverse in reverse order from n-1:

Answer: Because the calculated value of dp[ i+1 ][ j] is needed when calculating dp[ i ][ j ], and only the i+1th row is useful when calculating dii row dp, so here is actually You can also

optimize into a one-dimensional array:

dp[ j] = max(nums[ i ]-dp[ j ], nums[ j ]-dp[ j-1 ])

3. Thinking

Conventional ideas

Violent backtracking----->memory search------>dynamic planning

strong>

Similar topics include 1406 Stone Game 3

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

Label group:[dynamic programming

Hot topic

Game recommend

Game Popular