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 (dynamic programming) java

Release Time:2021-07-04 Topic:Source code of predicting winner index formula Reading:23 Navigation:Stock Liao information > Game > Leetcode 486. Winner prediction (dynamic programming) java phone-reading

1. 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.

LeetCode (LeetCode)

Original title link;

2. Proposal

After player 1 and player 2 have selected a round at the same time, the score difference between player 1 and player 2 is regarded as a sub-problem; when the first index of the array is i and the last index is j, expressed by dp[ i ][ j ], The final score difference between Player 1 and Player 2.

Loop equation:

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 ])

d

p

[

i

]

[

j

]

=

m

a

x

(

n

u

m

s

[

i

]

d

p

[

i

+

1

]

[

j

]

,

n

u

m

s

[

j

]

d

p

[

i

]

[

j

1

]

);

Then, when the basic solution is i==j, dp[ i ][ j] = nums[ i ]. The code implementation can be solved by recursion or loop.

Based on recursion:

class Solution {public boolean PredictTheWinner(int[] nums) {int[ ][] dp = new int[ nums.length ][ nums.length ]; int res = getDp(nums, 0, nums.length-1, dp); if(res <0) return false; return true;} public int getDp(int[] nums, int i, int j, int[ ][] dp) {if(i == j) return nums[ i ]; if(i> j) return 0; dp[ i ][ j] = Math.max(nums[ i]-getDp(nums, i+1, j, dp), nums[ j]-getDp(nums, i, j-1, dp)); return dp[ i ][ j ]; }}

Based on loop:

// improveclass Solution {public boolean PredictTheWinner(int[] nums) {int n = nums.length; int[ ][] dp = new int[ n ][ n ]; //initialization for (int i = 0; i = 0; i--) {for (int j = i + 1; j = 0; }}

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

Label group:[dynamic programming] [dp

Hot topic

Game recommend

Game Popular