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 (recursion, DP)

Release Time:2021-07-04 Topic:Source code of predicting winner index formula Reading:19 Navigation:Stock Liao information > Game > [LeetCode] 486. Winner prediction (recursion, DP) phone-reading

486. Predicted Winner

Questions of the same type: 877. Stone game

topic 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 points, predict whether player 1 will be 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. Reminder: 1=0.

When A first faces the interval [i...j ],

If A takes nums[ i ], then it becomes B first faces the interval [i+1...j] , The net victory of B vs. A in this interval is divided into dp[ i+1 ][ j ]; then the net victory of A vs. B should be nums[ i]-dp[ i+1 ][ j ]. If A takes nums[ j ], in the same way, the net victory of A against B is nums[ j]-dp[ i ][ j-1 ].

The larger of the above two cases is sufficient.

In summary, the state transition equation is as follows:

State transition equation: dp[ i ][ j] = max(nums[ i]-dp[ i + 1 ][ j ], nums[ j]-dp[ i ][ j-1 ])

Explanation 1.3

When initializing, dp[ i,i] =nums[ i ]; means If there is only one nums[ i] that can be taken, the first player takes it away, nums[ i] is the extra score

dp[ i,j] means that the first player gets nums from nums[ i] [j ], the maximum score more than the second player

For dp[i,j], the first player has two methods, one is to take the number at the beginning and the other is to take The ending number

If you take nums[ i] first, it means that the current score of the first player is nums[ i] + the opposite value of the maximum score obtained by the second player, which is dp[ i ,J] = nums[ i ]+(-dp[ i+1,j ]) where dp[ i+1,j] means the maximum score that the second player has more than the first player,

Similarly, if you take nums[ j] first, it means that the current score of the first player is the opposite of nums[ j] + the maximum score obtained by the second player, which is dp[ i ][j] = nums[ j ]+(-dp[ i,j-1 ]) where dp[ i,j-1] represents the maximum score that the second player has more than the first player

and each In one step, the first player wants to get the maximum score, and finally has a chance to win, so the final transfer equation is: dp[ i ][ j] =max{nums[ i ]+(-dp[ i+1,j] ), nums[ j ]+(-dp[ i,j-1 ])}

The last required value is dp[ 0,n-1 ], which is the number in the upper right corner of dp , To determine whether this number is greater than 0, greater than 0 means that there are more first-hand players than second-hand players, and they will win

How to fill in the form after writing the state transition equation?

AC code

public class Solution {// State transition equation: dp[ i ][ j] = max( nums[ i]-dp[ i + 1 ][ j ], nums[ j]-dp[ i ][ j-1 ]) public boolean PredictTheWinner(int[] nums) {int len ​​= nums.length; int[] [] dp = new int[ len ][ len ]; // dp[ i ][ j ]: As a first mover, the relative score that can be obtained by choosing in the interval nums[ i..j] for (int i = 0; i = 0; i --) {dp[ i ][ j] = Math.max(nums[ i]-dp[ i + 1 ][ j ], nums[ j]-dp[ i ][ j-1 ]);}} return dp[ 0 ][ len-1] >= 0; }}

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

Label group:[dp

Hot topic

Game recommend

Game Popular