Stone Game III

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";
}

};

Comments (6)