This is one of the easiest and fastest way to solve this DP problem.
class Solution {
public:
string stoneGameIII(vector& stoneValue) {
int n=stoneValue.size(),i,temp,temp1;
vector<int>dp(n,0);
dp[n-1]=stoneValue[n-1];
for(i=n-2;i>=0;i--)
{
//3 choices
//Take 1 stone only
dp[i]=stoneValue[i]-dp[i+1];
//Take 2 stones
temp=0;
if(i+2 < n)
{
temp=dp[i+2];
dp[i]=max(dp[i],stoneValue[i]+stoneValue[i+1]-temp);
}
//Take 3 stones
temp1=0;
if(i+3 < n)
{
temp1=dp[i+3];
}
if(i+2 < n)
{
temp=stoneValue[i+2];
}
dp[i]=max(dp[i],stoneValue[i]+stoneValue[i+1]+temp-temp1);
}
if(dp[0]==0)
return "Tie";
if(dp[0]>0)
return "Alice";
else
return "Bob";
}};