Home » 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.

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

READ  Target Sum

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions