for those who getting confused about bob's turn here is a tip to think of it... firstly we're only care about alice's score and our funtion only returns the alice score till here everything is fine.. the confusing part is bob's trun.. to understand it just image you as bob and you can only able to calculate what alice's score(through our func) if you make any move.. so as an opponent you try to make a move that force alice to have a least score possible... so we return that least score alice could score in bob's turn.. it is bit confusing but may be give you an another perspective to think of..
Almost solved it myself but forgot that res should be initialised with int_max in case of bob, made this change and code was accepted. Thank you for the video
To anyone who is confused by this problem Forget about code and solution Try to make recursive decision tree on small length array and you will be able to prove why is dp working here DP only works on overlapping sub problems, it is very easy to prove it for this problem if you try it using pen and paper Once you are able to solve it using pen and paper then write the code, I believe you will be able to write your own solution. And if you are not able to solve it then watching tutorial will help you click in what exactly you weren't thinking correctly.
I'm still a bit confused of the intuition behind minimizing bob's score. I thought we simple call backtrack without for his case without worrying about it's return. But doing it that way is not equivalent to minimizing his score. I need to mull over that for a few days to really understand it.
I was also confused by bob's turn Initially I thought the problem will become recursive with the same logic for both Alice and Bob (where both of them will try to maximise there score) so the solution will be max of ( total_sum - (recursively max possible for Bob in sub problem) ) , but later I realised that the goal of the game is for Alice to get max , where bob is not trying to max its own score but to minimise the score of Alice as much as it can , hope that helps
take inspirations from your stone gameIII solution, I tried to calculate the max diff of Alice -Bob, then return the sum of piles - diff divided by 2, it works!
@@gangstacoder4234 var stoneGameII = function (piles) { let cache = new Map() let sum = piles.reduce((acu, cur) => acu + cur, 0) function dfs(i, M) { if (i >= piles.length) { return 0 } if (cache.has(`${i}|${M}`)) { return cache.get(`${i}|${M}`) } let res = -Infinity let total = 0 for (let j = i; j < 2 * M + i; j++) { if (j >= piles.length) { break } total += piles[j] res = Math.max(res, total - dfs(j + 1, Math.max(M, j - i + 1))) } cache.set(`${i}|${M}`, res) return res } let diff = dfs(0, 1) return (sum + diff) / 2 };
Could anyone please clarify to me why use "not Alice" in both Alice & Bob's turn ? (in the res calculations) ? I really just didn't get that specific point. Otherwise all clear as usual! Thank you Neetcode!
consider initilally alice = True (it means its alice turn now),when we say " not alice " it will become bob's turn right because not alice will be false now,simillarly if its bobs turn now it means alice variable must be false ,so next turn would be alice so "not alice " will become true in that case. In simple terms if its alice's turn "alice == true",else if its bob's turn "alice == false" hope you understand.
@@ADITYA-fk1zy Thank you for trying to clarify! The main point of confusion for me, is that when we are calculating the result for Alice, we do a dfs for Bob's turn therefore dfs(not Alice, etc.) - This part quite clear- The problem is when we are doing bob's result and doing the dfs for the following turn (which is Alice) why aren't we doing dfs( Alice) that's where I am still a bit confused
@@business_central Because when you are doing bob's result, the current Alice is False, so for the following turn (which is Alice) the Alice has to be True, then you need a (!Alice) to turn Alice to True.
@@codertrucker3296 that was my understanding, but when we do that it would be wrong. We have to have dfs(not alice) for both, when next turn is Bob's and when the next one is Alice's.
The not just takes the negation. So not True -> False. not False -> True. This is a pretty trivial feature of any programming language. I would test it out in an ide yourself if you don't believe that it works.
Hi Neetocde, I was thinking of buying your course but as a broke college student the price is a bit too expensive as a yearly payment. Can you add a monthly payment option? i'll prefer having to pay even more than the current price (like over a year) if the monthly is low enough because i know it's really worth it.
This is similar to the minimax algorithm so you can refer to that as well. If you think about it the function only returns Alice's maximum value and in that recursion of that function it will be bobs turn as well ( also remember bob is not the starting player). So from Alice's perspective Bob would have to minimise his score for Alice to get the best score. If Bob also maximises his score then it could probably result in Bob having more stones even though he only starts second
@@parashararamesh4252 No, they both play optimally. It's just the same thing - minimizing opponents score or maximizing owns. Bob minimizes Alice score == maximizes his own.
Someone ELI5 why at 17:20 we are trying to minimise Alice's score, we are just not including it into the line 21 because the DFS returns BOBS SCORE!!?!?!?! Isnt the DFS returning Alice's score, and if this is the case shouldn't we also be maximising it.???
Hey guys I tried to implement this solution in js as follows var stoneGameII = function(piles) { //this problem can be solved using recursion with caching let dp = {} //the dfs has 3 parameters - //alice - to keep track of who is playing alice or bob //i to keep track of index we are at in piles //M defined in problem statement as we can only choose piles between index i to 2M i.e eithier the first pile or the first two pile or first 3 pile so on.... //this function returns the no of stones alice gets const dfs = (alice,i,M) =>{ //Base cases if(i === piles.length) return 0 if((alice,i,M) in dp) return dp[(alice,i,M)] //if it is alice turn we maximize the result , if it is bob's turn we minimize the result(stones alice gets) as both players play optimally let res = alice ? 0 : Number.MAX_SAFE_INTEGER let total = 0 for(let x = 1; xpiles.length) break //we subtract 1 as x begins at 1 and we wanna consider the ith pile too total += piles[i+x-1] console.log(total) //Now we wanna make the dfs call if(alice){ res = Math.max(res, total+dfs(false,i+x,Math.max(M,x))) } else{ //since the function returns alice stone so we do not add bob stones (total ) in case bob is playing res = Math.min(res,dfs(true,i+x, Math.max(M,x))) } } dp[(alice, i, M)] = res return res } return dfs(true,0,1) }; But i m getting wrong answer Can anyone help
