Problem Statement:-
Alice and Bob 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.
Alice and Bob take turns, with Alice 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 Alice and Bob play optimally, return the maximum number of stones Alice can get.
Link: https://leetcode.com/problems/stone-game-ii/description/
Problem Explanation with examples:-
Example 1
Input: piles = [2,7,9,4,4]
Output: 10
Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.
Example 2
Input: piles = [1,2,3,4,5,100]
Output: 104
Constraints
1 <= piles.length <= 1001 <= piles[i] <= 10<sup>4</sup>
Intuition:-
We can simulate a game here and in alice's turn we will try to maximize the score and in bob's turn we will try to minimize the score.
Carry 3 parameters: the number of piles allowed to take, the current index and the current player.
Return the maximum score alice can get.
Solution:-
Create a recursive function solve(m,i,ch) where m is the number of piles allowed to take, i is the current index and ch is the current player.
If the current index is greater than or equal to the length of the piles, return 0. (base case)
Initialize ans = 0 if ch == 0 which means it is alice's turn else initialize ans = inf which means it is bob's turn.
Initialize tot = 0 which will store the sum of the piles till each index.
Iterate over piles from 1 to 2*m+1 and if the current index + X is greater than the length of the piles, break.
Add the current pile to tot.
If ch == 0, it is alice's turn so update ans = max(ans,tot+solve(max(m,X),i+X,1)) else it is bob's turn so update ans = min(ans,solve(max(m,X),i+X,0)).
Return and.
Return solve(1,0,0) which means initially alice can take 1*2 pile, the current index is 0 and it is alice's turn.
Code:-
JAVA Solution
class Solution {
public int stoneGameII(int[] piles) {
int[][] memo = new int[piles.length][piles.length];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return solve(1, 0, 0, piles, memo);
}
private int solve(int m, int i, int ch, int[] piles, int[][] memo) {
if (i >= piles.length) {
return 0;
}
if (memo[i][m] != -1) {
return memo[i][m];
}
int ans = 0;
int tot = 0;
for (int X = 1; X <= 2 * m; X++) {
if (i + X > piles.length) {
break;
}
tot += piles[i + X - 1];
if (ch == 0) {
ans = Math.max(ans, tot + solve(Math.max(m, X), i + X, 1, piles, memo));
} else {
ans = Math.min(ans, solve(Math.max(m, X), i + X, 0, piles, memo));
}
}
memo[i][m] = ans;
return ans;
}
}
Python Solution
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
@cache
def solve(m,i,ch):
if i >= len(piles):
return 0
ans = 0 if ch==0 else float('inf')
tot = 0
for X in range(1,2*m+1):
if i + X > len(piles):
break
tot += piles[i+X-1]
if ch == 0:
ans = max(ans,tot+solve(max(m,X),i+X,1))
else:
ans = min(ans,solve(max(m,X),i+X,0))
return ans
return solve(1,0,0)
Complexity Analysis:-
TIME:-
The time complexity of add method is O(n^3**)** because of the nested loops and recursive calls.
SPACE:-
The space complexity is O(n^2) due to the memoization array memo with dimensions piles.length by piles.length.