class Solution { public boolean PredictTheWinner(int[] arr) { //dp playlist ques - 45 , use of gap strategy //finding total int n = arr.length , total = 0; for(int i = 0 ; i < n ; i++) total += arr[i]; //making the dp int [][]dp = new int[n][n]; //traversing & handling trivial cases and rest of the dp for(int gap = 0 ; gap < n ; gap++){ for(int i = 0 , j = gap ; j < n ; i++ , j++){ //when only one coin if(gap == 0) dp[i][j] = arr[i]; //i==j //when only 2 coin, you take maximum of 2 else if(gap == 1) dp[i][j] = Math.max(arr[i],arr[j]); //when more than 2 coins else{ /* if you chose ith coin , the opponent will choose the next coin such that you get minimum of next choice */ int cost1 = arr[i] + Math.min(dp[i+2][j],dp[i+1][j-1]); /* if you chose ith coin , the opponent will choose the next coin such that you get minimum of next choice */ int cost2 = arr[j] + Math.min(dp[i+1][j-1] , dp[i][j-2]); //but you will make choices such that you get max of cost1 //and cost2 dp[i][j] = Math.max(cost1 , cost2); } } } //now your final maximum score is in dp[0][n-1] , opponent score will be int opponent = total - dp[0][n-1]; //if opponent score is greater than yours return false else true return opponent > dp[0][n-1] ? false : true; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter