题目大意：
石子游戏 III
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 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。
示例 4：
输入：values = [1,2,3,-1,-2,-3,7] 输出："Alice"
示例 5：
输入：values = [-1,-2,-3] 输出："Tie"
提示：
1 <= values.length <= 50000-1000 <= values[i] <= 1000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1406
解题思路分析：
遇到这种有n种选择然后找最优解的问题，我们应该下意识想到使用动态规划DP来解题。我们在之前的文章多次讲过，动态规划实际上也是带记忆的递归。本文我们会分别给出这两种解法的代码。
首先，本题是一道游戏题目，游戏中有2个玩家。对于这种题，我们是不需要模拟出2个人物去解题的。实际上2个人的逻辑没有任何差别，对于任意一个人，当前都有3种选择（小于3堆时的选择会小于3种），选择拿1堆，2堆或者3堆。做出哪种选择取决于哪种选法能够使自身利益最大化。
解题时我们先建立一个递归函数，参数是当前index，以及当前剩下的石头的总分数sum。返回结果为当前index到数组末尾，当前玩家可以拿到最多的石头分数。由于此时我们无法判断出哪一种选择最优，因此我们必须对3种选择分别进行尝试（选择综合征的福音）。当选择第一堆石头后，当前index增加1，当前石头总量sum减少了第一堆石头的得分。我们将该情况递归到子问题中去求解。同理，我们选择前两堆石头后，index增加2，石头总量sum减少了前两堆石头的得分。选择前三堆石头也同理。
三个递归函数能够返回3种结果，这3种结果也是对手在当前用户做出每一种选择后给出的相应最优解。那么当前玩家该做出哪一种选择呢？显然让自身利益最大化，一定让对手利益最小化，因此三个结果中最小的一方应该是选择的对象，我们使用当前sum减去三种递归函数中最小的返回结果，就是当前递归函数的返回值。递归函数的终止条件是当前index是数组的最后一位时，当前用户别无选择，只能选择剩下的这一堆。
实现代码：
Integer[] memo; // 记忆数组
public String stoneGameIII(int[] stoneValue) {
memo=new Integer[stoneValue.length]; // 初始化记忆数组
int sum=0; // 计算所有石头的分数和
for(int val : stoneValue) sum+=val;
// 递归求出alice能够拿到的最多分数。
int aliceScroe=help(stoneValue,0,sum);
// 总分数减去alice的分数即是bob的分数
int bobScroe=sum-aliceScroe;
// 利用2人分数判断获胜方
if(aliceScroe>bobScroe) return "Alice";
else if(aliceScroe<bobScroe) return "Bob";
else return "Tie";
}
// stoneValue：石头数组
// index：当前下标
// sum：当前下标到数组结尾处所有石头的分数和
// 返回值：在当前下标后所有石头中，当前玩家能拿到的最大分数
int help(int[] stoneValue,int index,int sum){
// 如果下标越界，返回0
if(index==stoneValue.length) return 0;
// 如果下标是最后一位，别无选择，返回最后一个石头分数
if(index==stoneValue.length-1) return stoneValue[index];
// 如果记忆数组存在当前解，返回记忆数组中的值
if(memo[index]!=null) return memo[index];
int tempSum=sum;
// 循环3种选择（拿前1，2，3堆石头）
int min=Integer.MAX_VALUE;
for(int i=index;i<stoneValue.length&&i-index<3;i++){
// 总分数减去当前拿掉的分数
tempSum-=stoneValue[i];
// 递归求解找到一个最小值
min=Math.min(min,help(stoneValue,i+1,tempSum));
}
// 当前sum减去递归最小值为当前返回结果，存入记忆数组
memo[index]=sum-min;
return memo[index];
}本题解法执行时间为73ms。
Runtime: 73 ms, faster than 36.99% of Java online submissions for Stone Game III.
Memory Usage: 134 MB, less than 100.00% of Java online submissions for Stone Game III.
接下来我们看一下DP动态规划的解法。其实动态规划与递归思想没有任何差别。我们定义一个dp数组，dp[i]代表，第i位到数组结尾间能拿到的最大分数，如果想拿到最大分数，那么一定要让对手拿到最少分数，因此：
dp[i] = sum[i, length-1]-min(dp[i+1],dp[i+2],dp[i+2])
实现代码：
ic String stoneGameIII(int[] stoneValue) {
int[] dp=new int[stoneValue.length+1];
dp[stoneValue.length-1]=stoneValue[stoneValue.length-1];
int sum=stoneValue[stoneValue.length-1];
for(int i=stoneValue.length-2;i>=0;i--){
sum+=stoneValue[i];
int min=Integer.MAX_VALUE;
for(int j=i+1;j<=i+3&&j<=stoneValue.length;j++){
min=Math.min(min,dp[j]);
}
dp[i]=sum-min;
}
if(dp[0]>sum-dp[0]) return "Alice";
else if(dp[0]<sum-dp[0]) return "Bob";
else return "Tie";
}本题解法执行时间为6ms。
Runtime: 6 ms, faster than 97.82% of Java online submissions for Stone Game III.
Memory Usage: 48.6 MB, less than 100.00% of Java online submissions for Stone Game III.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1406-stone-game-iii-解题思路分析/