dp[i] 是取1个石头过来的,前面别人取的最大值是dp[i+1],我在位置 i 取的值就是 sum - dp[i+1]
dp[i] 是取2个石头过来的,前面别人取的最大值是dp[i+2],我在位置 i 取的值就是 sum - dp[i+2]
dp[i] 是取3个石头过来的,前面别人取的最大值是dp[i+3],我在位置 i 取的值就是 sum - dp[i+3]
取上面3种情况的max
classSolution{public:
string stoneGameIII(vector<int>& stoneValue){int i, n = stoneValue.size(), sum =0;
vector<int>dp(n+3,0);for(i = n-1; i >=0;--i){
sum += stoneValue[i];
dp[i]=max(max(sum-dp[i+3], sum-dp[i+2]),sum-dp[i+1]);}if(dp[0]> sum-dp[0])return"Alice";elseif(dp[0]< sum-dp[0])return"Bob";return"Tie";}};