企业官网建设流程全解析

Alice 和 Bob 继续他们的石子游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组stoneValue给出。

Alice 和 Bob 轮流取石子，Alice总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前1、2 或 3 堆石子。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是0。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取最优策略。

如果 Alice 赢了就返回"Alice"，Bob 赢了就返回"Bob"，分数相同返回"Tie"。

示例 1：

输入：values = [1,2,3,7]输出："Bob"解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]输出："Alice"解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。 如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。 如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。 注意，他们都应该采取最优策略，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]输出："Tie"解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

提示：

• 1 <= stoneValue.length <= 5 * 10^4
• -1000 <= stoneValue[i] <= 1000

分析：这道题是 486. 预测赢家 和 877. 石子游戏 的变体，解法上与 486 类似。设 Alice 的最终得分为 A，Bob 的最终得分为 B。如果 A>B，那么 Alice 获胜；如果 A<B，那么 Bob 获胜。而 A>B 可以变形为 A−B>0，因此只需关注得分之差 A−B 的值，而不是 A 和 B 具体是多少。从而每个玩家都需要最大化自己的得分减去对手的得分。令 dp[i] 代表从 i 开始到最后一堆石子里，当前玩家可以取得的最大石子数量。由于这道题取石子的方式有 3 种：取 1/2/3 堆，因此进行动态规划时，要考虑这三种情况，即：

dp[i]=max(stoneValue[i]-dp[i+1],

stoneValue[i]+stoneValue[i+1]-dp[i+2],

stoneValue[i]+stoneValue[i+1]+stoneValue[i+2]-dp[i+3])

最后检查 dp[0]，若大于 0，则 Alice 获胜；若小于 0，则 Bob 获胜；若等于 0，则平局。如果注意到 dp[i] 只依赖于 dp[i+1]，dp[i+2]，dp[i+3]，还可以将一维数组进一步优化为常数级空间。

int max(int a,int b) { return a>b?a:b; } char* stoneGameIII(int* stoneValue, int stoneValueSize) { int n=stoneValueSize,dp[n]; dp[n-1]=stoneValue[n-1]; if(n>=2)dp[n-2]=max(stoneValue[n-1]+stoneValue[n-2],stoneValue[n-2]-dp[n-1]); if(n>=3) { dp[n-3]=max(stoneValue[n-3]+stoneValue[n-2]+stoneValue[n-1],max(stoneValue[n-3]+stoneValue[n-2]-dp[n-1],stoneValue[n-3]-dp[n-2])); for(int i=n-4;i>=0;--i) dp[i]=max(stoneValue[i]+stoneValue[i+1]+stoneValue[i+2]-dp[i+3],max(stoneValue[i]+stoneValue[i+1]-dp[i+2],stoneValue[i]-dp[i+1])); } if(dp[0]>0)return "Alice"; else if(dp[0]<0)return "Bob"; return "Tie"; }