We’ll go over all the methods, including brute force and the most efficient way to solve this problem.
We are going to solve one of the problems of Leetcode by a different approach.
Problem Statement:
Alice and Bob continue their games with piles of stones. Several stones are arranged in a row, and each stone has an associated value, an integer given in the arraystoneValue.
Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row.
The score of each player is the sum of the values of the stones taken. The score of each player is 0 initially.
The game’s objective is to end with the highest score, and the winner is the player with the highest score, and there could be a tie. The game continues until all the stones have been taken.
Assume Alice and Bob play optimally.
Return "Alice" if Alice will win, "Bob" if Bob will win, or "Tie" if they end the game with the same score. Eg: - values=[1,2,3,7]
Output: “Bob” As Alice’s best move is only taking three stones at the same time, and, i.e., also less than seven so Bob is a winner in all aspects.
Explanation of the Problem Statement:
In this problem, there are two-player playing the game with piles of stones. Both the players will have to turn one by one.
Important Information in Question:
Two players are playing the pile of stone, i.e., Alice and Bob.
Each player’s turn comes one by one.
Alice will be the first player to start the game.
On each turn, each player has the choice of taking 1,2 or 3 stones from the remaining.
The initial score of both the players is initially 0.
The score is counted upon how many stones are handled by each player.
Winner of the game decides upon the highest number of the stone which player has.
The game will continue to be played until a single stone is present.
If, in the end, both have the same number of rocks, then the game is tied.
If Alice won, return “Alice” if Bob won return “Bob” else return “Tie.”
Now Take an Example To understand the Approach To deal with the Question:-
Seeing the Above example as a stoneValue array which contains four stones having different values 1, 2, 3, and 7, and Alice starts the game in the first stage, he has three choices either go for one or [1,2] or [1,2,3] bucket size stone, similarly for the remaining part of stone left, again Bob has also three choices to choose the number of stone 1, 2 or 3. This step continues to follow till we have the number of stones left.
For solving this question.”, As we see here, we are recursion 1, 2, or 3 bucket size stone numbers present in it. In the next step, also we repeat the same, so here some recursion is pointing out for this question.
Solution:
We are going to solve the problem in an optimized solution.
A possible solution for the Problem:-
Recursive Solution
Top-Down Approach
Bottom-Up Approach
Optimizing the Space, doing in constant Time.
Here we are going to start with the generic solution and move to an ideal solution.
Deciding Factor who has won the game here is the difference between the sum of no of stone value Alice and sum of no of stone Value Bob has :
If the difference is >0, until we have Alice winner as the first person to start the game is Alice.
If the difference is <0, then we have Bob winning as the second person is him.
If difference ==0, both Bob and Alice have the same sum of no of Stone Value.
Recursive Solution:
In this approach, we came with the idea for recursion. After doing one element, we move to the next element for the solution. We generally solve the problem for the next half in a similar manner, which is going till no more elements are left because of that idea of Recursion hit here. One more important point here is the base condition, which is simple: when we exceed the number of stones, then we have to return 0 because anything beyond that is meaningless to calculate.
Algorithm for the Recursive Solution:
Take the “N” size of stones which has a value specified for each one.
Declare the function helper for finding the solution.
First, pass the stoneValue array of size N to the helper function.
Now Calculate the ans when the player selects 1 stone and store the value.
Now Calculate the ans when the player selects 2 or 3 stone.
In each stage, when we choose stone, keep the maximum value in the answer.
At last, return the answer, with the base condition when no stone remains.
Value of Answer is calculated as the sum value specified on stone for no. of stone taken at a single time.
Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise, she will lose.
Top-Down Approach:
In seeing the Recursive Approach solution, we find some of part of the sequence we are solving like [ 3, 7] because of gets we get the idea of using Dynamic Programming, as we solve the problem From Top part start storing the solution by creating an extra space of N size, in which we insert the solution and calling the function in future we make separate condition else we have a solution then we directly return that.
Algorithm for the Top-Down Solution:
We have to declare and dp array of extra “N” size as we have to store the solution. In the future, if needed, we directly find in O(1) times.
All the remaining steps of the Recursive Approach are the same here.
Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise, she will lose.
Time Complexity: Time Complexity for the solution is O(N).
Space Complexity: O(N), because we’re taking extra space.
Bottom-Up Approach:
In Dynamic Programming, the question is solved in Bottom-Up Approach also, for that purpose, we require three values, if we are at “idx,” then we needed three values idx+1,+2,+3 respectively, moving from Bottom to Up, as we require a solution for 1, 2 or 3 no of stone.
Algorithm for the Bottom-Up Solution:
We are creating a DP array of size N+1 initialized all with the value of “0”.
We start iteration from the last index and continue till idx>=0.
We repeat the step of Recursive Approach logic for finding the solution for taking 1, 2, or 3 no of stone and summing the value of it.
After that it is its,taking the max of all 3 in the Dp array.
The final answer we get from the idx=0 as we fill the max value of the solution.
Then return the Winner’s name.
Code for the Bottom-Up Approach:
import java.util.Scanner;
publicclass Stonegame_BUA { publicstaticvoidmain(String [] args){ Scanner sc=new Scanner(System.in); int n= sc.nextInt(); int [] stoneValue=newint[n]; for(int i=0;i<n;i++){ stoneValue[i]= sc.nextInt(); } int len=stoneValue.length; int [] dp=newint[len+1]; int idx=len-1; while (idx>=0){ int ans=Integer.MIN_VALUE; ans=Math.max(ans,stoneValue[idx]-dp[idx+1]); if(idx+1<stoneValue.length){ ans=Math.max(ans,stoneValue[idx]+stoneValue[idx+1]-dp[idx+2]); } if(idx+2<stoneValue.length){ ans=Math.max(ans,stoneValue[idx]+stoneValue[idx+1]+stoneValue[idx+2]-dp[idx+3]); } dp[idx]=ans; idx--; } int winner=dp[0]; if(winner>0){ System.out.println("Alice"); } elseif(winner<0){ System.out.println("Bob"); } else { System.out.println("Tie"); } } }
Input:
4
1 2 3 6
Output:
“Tie”
Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise, she will lose.
Time Complexity:Time Complexity is also O(N) because we are filling the solution for the “idx” location and then return the solution at idx=0, in O(1).
Space Complexity: Space requires as we create an N+1 size extra array for that, so Space Complexity is O(N)
Space Optimization:
As seen above all things of solving require only three values only to fill the DP array.
For fill the dp[i] we require only dp[i+1], dp[i+2] and dp[i+3] to fill the i th position.
Similar Manner, it goes on. As for that, we require not to create the DP array of size N, this can be done by using three variables from which we get a max of all the values, and by this, we fill i the index, updating the answer at last at idx=0 we return an answer. Hence Time Complexity remains O(N), but we optimized the space here from O(N) to O(1).
dp[i]
dp[i+1]
dp[i+2]
dp[i+3]
X
X
X
Algorithm for the Space Optimization:
We declare three variables initially having assigned value to 0.
Now find the value of the answer by taking 1, 2, a, or 3 stones, and repeat for the remaining stone.
Now updating the value by Bottom-up manner for three variables.
dp_3=dp_2 , dp_2=dp_1, dp_1=ans.
4. Now repeat the step till no stone remains.
5. After that, all the stone is complete the dp_1 value will give us the answer.
6. After that, we check the condition and return the parameter.
Code for the Space Optimization:
import java.util.Scanner;
publicclass Stonegame_BUA { publicstaticvoidmain(String [] args){ Scanner sc=new Scanner(System.in); int n= sc.nextInt(); int [] stoneValue=newint[n]; for(int i=0;i<n;i++){ stoneValue[i]= sc.nextInt(); } int len=stoneValue.length; int dp_1=0,dp_2=0,dp_3=0; int idx=len-1; while (idx>=0){ int ans=Integer.MIN_VALUE; ans=Math.max(ans,stoneValue[idx]-dp_1); if(idx+1<stoneValue.length){ ans=Math.max(ans,stoneValue[idx]+stoneValue[idx+1]-dp_2); } if(idx+2<stoneValue.length){ ans=Math.max(ans,stoneValue[idx]+stoneValue[idx+1]+stoneValue[idx+2]-dp_3); } dp_3=dp_2; dp_2=dp_1; dp_1=ans; idx--; } int winner=dp_1; if(winner>0){ System.out.println("Alice"); } elseif(winner<0){ System.out.println("Bob"); } else { System.out.println("Tie"); } } }
Input:
4
1 2 3 6
Output:
“Tie”
Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise, she will lose.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) as we are not consuming any extra space.
Frequently Asked Question:
1). What is Recursion?
Ans: Calling the function over a defined base condition to solve the sub-task for a repeated solution.
2). What is the Best Time Complexity for the Stone Game III problem?
Ans: Time Complexity is O(N), and Space Complexity is O(1) by using Dynamic Programming and three defined variables required to do the task.
3). How do we approach the Dynamic Programming Problem?
Ans: Using Top-Down and Bottom-Up Approach.
Key TakeAway:
In this blog, we take a problem, understand its solution in Recursive Approach and make way for the Dynamic Programming, as repetition is occurring storing in DP array then after moving to Top-Down and Bottom-Up Approach after that seeing the constraint present in the question for taking 1, 2 or 3 stones using that declares three variable for storing the solution for each, then after using no extra space as only for constant space for the three variable. So, Therefore the Main purpose is to take a problem and optimize the solution to the best of knowledge.
34+ registered 
