Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]
. The objective of the game is to end with the most stones.
Alex and Lee take turns, with Alex starting first. Initially, M = 1
.
On each player's turn, that player can take all the stones in the first X
remaining piles, where 1 <= X <= 2M
. Then, we set M = max(M, X)
.
The game continues until all the stones have been taken.
Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.
For Example:
Input:
[2,7,9,4,4]
Output:
10
Logic:
You can easily solve this question recursion.
So Alex will try to get the maximum point as he is playing optimally
if player == 1 (or Alex)
alexPoint = max(alexPoint, sum[s to s+x-1] stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));
also, Lee is playing optimally and try to reduce Alex points
if player == 0 (or Lee)
alexPoint = min(alexPoint, stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));
1<=x<2*M
Will this solution gives TLE?
Yes
as 1<=N<=100 (total number of piles)
We can't use recursion here.
How can we optimize it?
One solution that I think of is using memorization. We can create a matrix say dp
and store current state dp[s][m][p]
s -> starting index
m -> for picking stones from piles i.e (1<=x<=2*m)
p -> 0/1 (Lee/Alex)
Now if we reach this state again we don't need to compute again and return dp[s][m][p]
(Yahi battein to bad me yaad ayengi 😛)
Can we further optimize it?
Yes.
For calulationg sum[s to s+x-1]
we can use prefixSum array
so sum[s to s+x-1] will be prefixSum[s+x-1] - prefixSum[s-1]
To View My Solution:
https://github.com/shivam04/codes/blob/master/leetcode/stone-game-ii.cpp
No comments:
Post a Comment