leetcode.1406. 石子游戏 III

1406. 石子游戏 III

设代表该玩家在区间内的最大值，那么一定是等于减去上一个玩家在区间的最小值
上一个玩家可能取了一个，两个或者三个。
所以可以有，;

class Solution {
public:
    int dp[50005];
    string stoneGameIII(vector<int>& a) {
        int sum=0,n=a.size();
        dp[n]=0;
        for(int i=n-1;i>=0;i--){
            sum+=a[i];
            int ans=dp[i+1];
            for(int j=1;j<=3&&i+j<=n;j++)
            ans=min(ans,dp[i+j]);
            dp[i]=sum-ans;
        }
        if(dp[0]==sum-dp[0])return "Tie";
        if(dp[0]>sum-dp[0])return "Alice";
        return "Bob";
    }
};