Q45 Predict the Winner - LeetCode 486
Thu Mar 30 2023 10:46:05 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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;
}
}
content_copyCOPY
https://leetcode.com/problems/predict-the-winner/
Comments