Stone Game II - Leetcode 1140 - Python

[@ary_21]

At 11:42 i realised Alice and Bob are playing with me and not with each other

[@LasTCursE69]

This is by far the most confusing problem I've encountered on leetcode..

[@sarwesharivazhagan5085]

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..

[@ankitkushwaha8577]

Thanks bro

[@reckyru]

DP is pain and makes me cry

[@voidpointer398]

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.

[@Antinormanisto]

I still don't understand what the hell is going on and what do I do

[@TheLearningLab898]

you not alone bro🫂

[@satyadheeraj6081]

@@TheLearningLab898 same here man 🥹

[@thunder_cs]

same

[@erickjhormanromero6905]

Same

[@ParodyCSEDept]

I am really happy to find that this video has word by word the same logic which I used to solve this one

[@apputadhiyal9451]

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

[@sahilthukral4948]

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

[@MP-ny3ep]

Phenomenal explanation. Thank you!

[@Calypso1406]

idk how to come up with these kinds of solutions and im genuinely lost

[@朴云峰]

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]

hey i tried that too...can you elaborate or paste the code (if possible)

[@朴云峰]

@@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 };

[@tofahub]

This one is more helpful@@朴云峰

[@siddhantvishnu4309]

Exactly what I had in mind. Just had a few isues coding it up. Great video

[@namandubey8348]

i wonder how long will it me to solve these kind of problem by myself

[@6kostia]

Nice solution, but it's better to ignore Bob's existence, Alice plays against herself as Bob and Alice are actually the same player.

[@ivanzaplatar9033]

This is what I was thinking. What would the recurrence relation be?

[@6kostia]

@@ivanzaplatar9033 res = max(res, (sum(piles[i:])- dfs(i + x, max(x, m)))) It actually runs faster, around 200 ms

[@NeetCodeIO]

Does the sum(piles[I:]) run in O(n) time? I believe that may affect the overall time complexity

[@ADITYA-fk1zy]

​@@NeetCodeIO we pre-compute the suffixsum in a array and use that array so it's O(1) to get sum.

[@RomanFalcon13]

Thank you king, keep it up!

[@lesterdelacruz5088]

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.

[@dudeyouhavenoidea]

I am equally confused, after watching stone game 1, I thought we just ignore bob score and only focus on Alices stone

[@luizfelipe2330]

For sure this one is one of the best videos that you did.

[@user-le6ts6ci7h]

The time complexity you mentioned is not correct, m might at the worst go up to log(n)

[@mutianzhu5128]

Reminds me of minimax algorithm.

[@jaatharsh]

true saviour, thanks once again

[@ayo4590]

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.

[@NeetCodeIO]

Feel free to email me at neetcodebusiness@gmail

[@sheruloves9190]

Simply amazing!!

[@kotik1221]

Do you have this code snippet somewhere? I want to read the code in my own editor.

[@business_central]

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!

[@ADITYA-fk1zy]

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.

[@business_central]

@@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

[@codertrucker3296]

@@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.

[@business_central]

@@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.

[@NeetCodeIO]

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.

[@theman-d]

I havethis error "" TypeError: inf is not valid value for the expected return type integer ""

[@saagerbabung5652]

In Google interview, do they accept memorization solution or it has to be only tabulation form for a DP problem?

[@AsliArtist]

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.???

[@adwinsanjo]

Since its Bob's turn. Bob tries to maximise his own score and minimises Alice's score as he is playing optimally

[@pilot615]

Now I have just understood!

[@MohddAlii]

Why are you minimising at bob's turn, Will bob not play optimally?

[@lakshmanvengadesan9096]

Bob is minimizing the score of Alice, not his score

[@parashararamesh4252]

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

[@alek4001]

@@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.

[@aesophor]

@@lakshmanvengadesan9096 Holy shit this comment should be pinned

[@johnnychang3456]

Bob will get Alice's score from the recursive call, of which he'll select the minimum one.

[@liangyu3771]

life saver. I could not understand the question (sad)

[@twoPointers123]

knock knock , is this a Minimax algorithm

[@PriyanshuTyagi-ts2uw]

Thanks!

[@uptwist2260]

Thanks for the daily

[@vamsikrishnagannamaneni912]

Good God !

[@arnabchatterjee2094]

a typical min max algo kinda tic tac toe ai

[@alphaOrderly]

I can't understand problem

[@AdamUngier]

It was my first time experiencing a dynamic programming problem and I am completely and utterly confused, how does your brain think of this stuff?

[@OmarAlimammadzade-v7s]

why we create variable total?

[@MrKB_SSJ2]

Yeeeeeeee

[@meghasharma_0419]

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

[@prashantshubham]

Issue is with your hash map i.e `dp` implementation

[@meghasharma_0419]

@@prashantshubham Thanks