Stock Liao information

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

"Predicting Winners"-the road to optimization from recursion to dynamic programming

Release Time:2021-07-04 Topic:Imitate the predictive winner index formula Reading:19 Navigation:Stock Liao information > Game > "Predicting Winners"-the road to optimization from recursion to dynamic programming phone-reading

This is a topic of Likou:

If you don’t know how to do it, you can go to see the solution for yourself, it's very detailed.

Here I mainly write down my own course from recursive optimization to dynamic programming (spatial optimization). (The code can pass through the oj of Likou)

Recursion:

1 class Solution { 2 public : 3 int dfs(vector&nums, int left, int right) 4 { // The meaning of dfs here Is the difference between the score of the player currently operating and the score of another player 5 if(left == right) 6 return nums[ left ]; 7 return max(nums[ left]-dfs( nums,left+ 1,right),nums[ right ]-dfs(nums,left,right- 1 )); 8 } // Because "the player’s play style will maximize his score, the current player tries his best to choose a strategy with a higher score than the opponent 9 bool PredictTheWinner(vector& nums) { 10 return dfs(nums, 0,nums.size()- 1) >= 0; // The difference between one's own score and the other's score The difference is not less than 0. Your own score is not less than the opponent's score 11 } 12 };

Time efficiency is very low, so upgrade:

Memoized recursion :

1 class Solution { 2 public : 3 int memory[ 20 ][ 20 ]; // Since the data range has been given, directly define the size of the array 4 int dfs(vector&nums, int left, int right) 5 { // The meaning of dfs here is the score of the current player and another player The difference between the scores 6 if(memory[ left ][ right ]!=- 1 ) 7 return memory[ left ][ right ]; 8 if(left == right) 9 { 10 memory[ left ][ right ]= nums[ left] ; 11 return nums[ left ]; 12 } 13 int ans = max(nums[ left]-dfs(nums,left+ 1,right),nums[ right ]-dfs(nums, left,right- 1 )); 14 memory[ left ][ right] = ans; 15 return ans; 16 } // Since "the player’s gameplay will maximize his score, so the current Players try their best to choose strategies that score higher than their opponents 17 bool PredictTheWinner(vector& nums) { 18 memset(memory,- 1, sizeof (memory)); 19 return dfs(nums, 0,nums.size()- 1) >= 0; // The difference between your own score and the opponent's score is not less than 0. Then your own score is not less than the opponent's score 20 } 21 20 } 21 span> };

The efficiency is greatly improved

Then by summarizing the recursive recursion formula, it is not difficult to think of using dynamic programming instead of recursion:

Dynamic programming:

1 class Solution { 2 public : 3 int dp[ 20] [ 20 ]; 4 bool PredictTheWinner(vector& nums) { 5 for( int i = 0;i

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

Label group:[dynamic programming] [Recursion] [dfs

Hot topic

Game recommend

Game Popular