Do you think IIT Guwahati certified course can help you in your career?
Introduction
Using Dynamic Programming, we solve each subproblem just once and then remember the result, avoiding the need to recalculate the answer for similar subproblems in the future. It is the most effective design strategy for dealing with problems involving optimization. Computer networks, routing, graph problems, computer vision, artificial intelligence, machine learning, and many other fields utilize dynamic programming extensively.
This blog will discuss one such problem, Stone Game VII, and solve it using dynamic programming.
Problem Statement
Alice and Bob are 2 kids playing a game, and they take turns to make a move. Alice starts first.
There are N stones placed in a row, and in one move, the player can either remove the leftmost stone or the rightmost stone from this row. They receive points equal to the sum of the values of the remaining stones. When no more stones are left in this row, the one with the higher score is declared the winner.
Bob realizes that he will always lose the game, and his main aim is to minimize the difference in their scores. In contrast, Alice tries to maximize the difference in the scores.
You are given an array of integers, STONES, where STONES[i] represents the value of the i-th stone from the left. Your task is to determine the difference in the scores of Alice and Bob if they both play the game optimally.
Let us try to understand the question with the help of an example.
Example
STONES[] = {5, 3, 1, 4, 2}
Let us suppose that the score of Alice is ASCORE and that of Bob is BSCORE. → In the first move, Alice will remove the stone from the end, i.e, one with the value 2.
ASCORE = 5 + 3 + 1 + 4
= 13
BSCORE = 0
STONES = {5, 3, 1, 4}
→ Now Bob will remove the stone with the value 5.
ASCORE = 13
BSCORE = 0 + 3 + 1 + 4
= 8
STONES = {3, 1, 4}
→ In her turn, Alice will remove the stone with the value 3.
ASCORE = 13 + 1 + 4
= 18
BSCORE = 8
STONES = {1, 4}
→ Bob will remove the stone with the value 1.
ASCORE = 18
BSCORE = 8 + 4
= 12
STONES = {4}
→ Alice will remove the stone with the value 4.
ASCORE = 18
BSCORE = 12
STONES = { }
Difference between scores = 18 - 12 = 6
Now let us try to solve this problem using Dynamic Programming.
Approach 1
Since Alice wants to maximize the score, she will try to pick the stone to maximize the difference in their scores.
Suppose if she picks a stone i from the start, then the total points Alice will get is equal to Alice = Total sum - STONE[i].
If she picks a stone j from the end, then the total points, in this case, will be equal to Alice = Total sum - STONE[j].
After this step, the total points that Bob will score will be equal to Bob = min(Total sum - STONE[i], Total sum - STONE[j])
We will apply the above approach to decide which stone to pick each time a player’s turn. Since, this is a recursive approach, the same value is computed again.
Algorithm
First, we calculate the sum of the values of all the stones.
If, at any point, the sum becomes negative, we stop the further process.
We continue this process only if a subarray exists, i.e., i > j.
We first check if we have already calculated the answer of the sub-problem before and if that’s the case, we return it.
Otherwise, for every i and j, we will consider both the possibilities(picking the leftmost stone and picking the rightmost stone) and check in which case the difference will be maximum.
Program
// C++ solution for Stone Game VII using dynamic programming.
// C++ program to find the difference in the scores of Alice and Bob if they play optimally.
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
// Helper recursive function that will find the difference in the scores.
int getMaxDiff(vector<int> &v, int i, int j, int sum)
{
// Base case.
if (i >= j || sum < 0)
return 0;
// Compute the two possibilities.
int x = sum - v[i] - getMaxDiff(v, i + 1, j, sum - v[i]);
int y = sum - v[j] - getMaxDiff(v, i, j - 1, sum - v[j]);
// Return the max of both possibilities.
return max(x, y);
}
// Function to find the difference in the scores of Alice and Bob if they play optimally.
int stoneGameVII(vector<int> &stones)
{
int sum = 0;
// Finding the sum of values of all the stones.
for (auto i : stones)
sum += i;
// Calling the recursive function to find the answer.
return getMaxDiff(stones, 0, stones.size() - 1, sum);
}
int main()
{
int n, a;
vector<int> stones;
// Taking user input.
cout << "Enter the number of stones: ";
cin >> n;
cout << "Enter the values of the stones:\n";
for (int i = 0; i < n; i++)
{
cin >> a;
stones.push_back(a);
}
// Calling the function and printing the answer.
cout << "The difference in the scores of Alice and Bob if they play optimally is " << stoneGameVII(stones);
}
You can also try this code with Online C++ Compiler
The difference in the scores of Alice and Bob if they play optimally is 6.
Time Complexity
The time complexity is given by O(2 ^ N), where N is the total number of stones in the row. Since each function spawns two recursive calls of itself and the depth of the recursive tree is O(N), the total number of recursive calls will be of the order of O(2 ^ N).
Space Complexity
The space complexity is O(N), where N is the number of stones. It is because the depth of the recursion stack can be at most of the order of O(N).
In this approach, we will implement the same fundamental idea described in approach 1 but in this approach we will use DP with memoization. We will store the answer for each subproblem as we encounter it, so that we don’t have to recompute it.
Algorithm
First, we calculate the sum of the values of all the stones.
Then we create a 2-D DP array that stores the subarray's answer starting from an index i and ending at an index j.
If, at any point, the sum becomes negative, we stop the further process.
We continue this process only if a subarray exists, i.e., i > j.
We first check if we have already calculated the answer of the sub-problem before and if that’s the case, we return it.
Otherwise, for every i and j, we will consider both the possibilities(picking the leftmost stone and picking the rightmost stone) and check in which case the difference will be maximum.
Program
// C++ solution for Stone Game VII using dynamic programming.
// C++ program to find the difference in the scores of Alice and Bob if they play optimally.
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int dp[1002][1002];
// Helper recursive function that will find the difference in the scores.
int getMaxDiff(vector<int> &v,int i,int j,int sum)
{
// Base case.
if (i >= j || sum <0)
return 0;
// To avoid recalculations.
if (dp[i][j] !=-1)
return dp[i][j];
return dp[i][j] = max(sum - v[i] - getMaxDiff(v, i +1, j, sum - v[i]), sum - v[j] - getMaxDiff(v, i, j -1, sum - v[j]));
}
// Function to find the difference in the scores of Alice and Bob if they play optimally.
int stoneGameVII(vector<int> &stones)
{
// Initializing dp matrix with -1.
memset(dp,-1,sizeof(dp));
int sum =0;
// Finding the sum of values of all the stones.
for (auto i : stones)
sum += i;
// Calling the recursive function to find the answer.
return getMaxDiff(stones,0, stones.size() -1, sum);
}
int main()
{
int n, a;
vector<int> stones;
// Taking user input.
cout <<"Enter the number of stones: ";
cin >> n;
cout <<"Enter the values of the stones:\n";
for (int i =0; i < n; i++)
{
cin >> a;
stones.push_back(a);
}
// Calling the function and printing the answer.
cout <<"The difference in the scores of Alice and Bob if they play optimally is " << stoneGameVII(stones);
}
You can also try this code with Online C++ Compiler
The difference in the scores of Alice and Bob if they play optimally is 6.
Time Complexity
The time complexity is given by O(N), where N is the total number of stones in the row. Since we are traversing the row with N stones only once, the time complexity is given by O(N).
Space Complexity
The space complexity is O(K2), where K is the size of the dp array. This is because we are taking a dp array, DP[K][K], to store the results of the sub-problems and hence find the answer.
Key Takeaways
So, this blog discussed the problem of Stone Game VII and how to solve it using dynamic programming. To learn more and practice some more dynamic programming problems, head over to Coding Ninjas Studio and crack your interviews like a Ninja!
Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.
34+ registered 
