leetcode 1406. 石子游戏 III 困难

Alice 和 Bob 继续他们的石子游戏。几堆石子排成一行每堆石子都对应一个得分由数组stoneValue给出。Alice 和 Bob 轮流取石子Alice总是先开始。在每个玩家的回合中该玩家可以拿走剩下石子中的的前1、2 或 3 堆石子。比赛一直持续到所有石头都被拿走。每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是0。比赛的目标是决出最高分得分最高的选手将会赢得比赛比赛也可能会出现平局。假设 Alice 和 Bob 都采取最优策略。如果 Alice 赢了就返回AliceBob 赢了就返回Bob分数相同返回Tie。示例 1输入values [1,2,3,7]输出Bob解释Alice 总是会输她的最佳选择是拿走前三堆得分变成 6 。但是 Bob 的得分为 7Bob 获胜。示例 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 的最终得分为 ABob 的最终得分为 B。如果 AB那么 Alice 获胜如果 AB那么 Bob 获胜。而 AB 可以变形为 A−B0因此只需关注得分之差 A−B 的值而不是 A 和 B 具体是多少。从而每个玩家都需要最大化自己的得分减去对手的得分。令 dp[i] 代表从 i 开始到最后一堆石子里当前玩家可以取得的最大石子数量。由于这道题取石子的方式有 3 种取 1/2/3 堆因此进行动态规划时要考虑这三种情况即dp[i]max(stoneValue[i]-dp[i1],stoneValue[i]stoneValue[i1]-dp[i2],stoneValue[i]stoneValue[i1]stoneValue[i2]-dp[i3])最后检查 dp[0]若大于 0则 Alice 获胜若小于 0则 Bob 获胜若等于 0则平局。如果注意到 dp[i] 只依赖于 dp[i1]dp[i2]dp[i3]还可以将一维数组进一步优化为常数级空间。int max(int a,int b) { return ab?a:b; } char* stoneGameIII(int* stoneValue, int stoneValueSize) { int nstoneValueSize,dp[n]; dp[n-1]stoneValue[n-1]; if(n2)dp[n-2]max(stoneValue[n-1]stoneValue[n-2],stoneValue[n-2]-dp[n-1]); if(n3) { 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 in-4;i0;--i) dp[i]max(stoneValue[i]stoneValue[i1]stoneValue[i2]-dp[i3],max(stoneValue[i]stoneValue[i1]-dp[i2],stoneValue[i]-dp[i1])); } if(dp[0]0)return Alice; else if(dp[0]0)return Bob; return Tie; }