Home » Technical Interview Questions » Dynamic Programming Interview Questions » Stone Game II Leetcode

# Stone Game II Leetcode

## What is Stone Game II Problem?

Stone Game II LeetCode is a very famous problem on leetcode which is solved using the DP approach. The statement of the problem is described as two players A and B are playing a stone game. There are N number of piles each pile containing some stones. Player A will always start the game. A and B are supposed to pick all the stones in first X piles where  1<=X<=2M (initially M = 1)  one by one until no more piles are left. The objective is to end the game with Player A having maximum stones. Print the maximum stones that can be collected by Player A.

As the total possible stones of Player A can be 8 or 10, the output will be maximum of all possible outcomes i.e. 10.

## Example

Input

piles = [5, 3, 4, 5]

Output

10

Input

piles = [2, 7, 9, 4, 4]

Output

10

## Dynamic Programming Method

### Algorithm

1. Initialize a list containing piles of stones.
2. Create an array sum of size n+1.
3. Update the sum array with the number of stones in each pile.
4. Create a 2D-DP array and set all values as 0.
5.  Store the values in sum array in the last dp array.
6. Traverse and update dp array as dp[i][j] = max(dp[i][j], sum[i] – dp[i+x][max(j,x)]).
7. Return the maximum stones of player A.

Time Complexity: O(n3)

Space Complexity: O(n2)

### C++ Program for Stone Game II Leetcode

```#include<bits/stdc++.h>
using namespace std;

class Stone{
public:
int stoneGameII(vector<int>& piles) {
int n = piles.size();
if(n == 0)
return 0;

vector<int>sum(n+1, 0);

for(int i=n-1; i>=0; i--){
sum[i] = piles[i] + sum[i+1];
}

vector<vector<int>>dp(n+1, vector<int>(n+1,0));
for(int i = 0; i <= n; i++){
dp[i][n] = sum[i];
}

for(int i=n-1; i>=0; i--){
for(int j=n-1; j>=0; j--){
for(int x=1; x<=2*j && i+x<=n; x++)
dp[i][j] = max(dp[i][j], sum[i] - dp[i+x][max(j,x)]);
}
}
return dp[0][1];
}
};

int main(){

Stone s;
vector<int> piles = {5, 3, 4, 5};
cout<<s.stoneGameII(piles);

}```
`10`

### Java Program for Stone Game II Leetcode

```import java.util.*;
class Stone{

static int stoneGameII(int[] piles){
int n = piles.length;
if(n == 0)
return 0;

int[] sum = new int[n+1];
int[][] dp = new int[n+2][n+2];

for(int i=0; i<n; i++){
sum[i]=0;
}

for(int i=n-1; i>=0; i--){
sum[i] = piles[i] + sum[i+1];
}

for(int i = 0; i <= n; i++){
dp[i][n] = sum[i];
}

for(int i=n-1; i>=0; i--){
for(int j=n-1; j>=0; j--){
for(int x=1; x<=2*j && i+x<=n; x++){
dp[i][j] = Math.max(dp[i][j], sum[i] - dp[i+x][Math.max(j,x)]);
}
}
}

return dp[0][1];
}

public static void main (String[] args){

int piles[] = {5, 3, 4, 5};

System.out.println(stoneGameII(piles));
}
}```
`10`

References