https://leetcode.com/problems/predict-the-winner/ Please check this question out on leetcode and can anyone tell me why my code wont work?
class Solution {
public boolean stoneGame(int[] piles) {
int total=0;
for(int pile:piles)total+=pile;
int [][]dp=new int[piles.length][piles.length];
for(int []arr:dp)Arrays.fill(arr,-1);
int alice=recursion(0,piles.length-1,piles,true,dp);
int bob=total-alice;
return alice>bob;
}
public int recursion(int start,int end,int []piles,boolean alice,int [][]dp){
if(start>end){
return 0;
}
if(dp[start][end]!=-1)return dp[start][end];
if(alice){
int stTake=piles[start]+recursion(start+1,end,piles,false,dp);
int endTake=piles[end]+recursion(start,end-1,piles,false,dp);
return dp[start][end]=Math.max(stTake,endTake);
}
else{
int stTake=piles[start]+recursion(start+1,end,piles,true,dp);
int endTake=piles[end]+recursion(start,end-1,piles,true,dp);
return dp[start][end]=Math.min(stTake,endTake);
}
}
}
Auto comment: topic has been updated by anushkanocoding (previous revision, new revision, compare).
It is working, I literally copy-pasted your solution and got AC just change the function name to
public boolean predictTheWinner(int[] piles)
Edit — Why do you keep editing your code and adding more mistakes?
Sorry i accidentally copy-pasted the solution that was working. I edited the code just now. This is the one that doesnt seem to work. Edit-Can you tell me what the mistake is this code? i cant seem to figure it out.
Auto comment: topic has been updated by anushkanocoding (previous revision, new revision, compare).
First of all the condition should be
alice>=bob
(read the last paragraph of the problem). Then you need to change your logic for when it is Bob's turn to not addpiles[start]
orpiles[end]
to Alice's score.why does this code work for https://leetcode.com/problems/stone-game/description/ this question then?
Your code always returns true since
recursion
always returns the total of the array. Turns out the answer to that problem is also coincidentally always true lol (see editorial approach 2).oh that makes sense thank you.