Stone Game II Leetcode

Table of Contents

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.

Stone Game II Leetcode

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

Input

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

Output

Dynamic Programming Method

Algorithm

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

Time Complexity: O(n³)

Space Complexity: O(n²)

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

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

References