Stone Game II Leetcode

Difficulty Level Medium
Frequently asked in Game Theory Google
algorithms coding Dynamic Programming Interview interviewprep LeetCode LeetCodeSolutionsViews 3550

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 

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

Translate »