题目描述: 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 方法1： 主要思路： （1）dp[ i ]表示从当前第 i 个元素起，到最后的元素，使用1，或2，或3堆，用 j 表示，可以获得最优的结果； （2）sum表示从当前第 i 个元素到最后一个元素的之和，则在 i 处取完 j 堆之后，则剩下的最优的取法获得值为 dp[i+j]，由于总数不变，故dp[ i ]+dp[ i+j ]=sum，故在 i 处的最优的结果即为三种取法中的最优的结果，既 dp[i]=max(dp[i],sum-dp[i+j]);，j取 1,2,3； （3）为了便于处理，将dp多申请了三个元素的内存，并对后面三个元素赋值为0，减少对前面的影响，其它元素初始化赋值为INT_MIN； （4）最后根据sum和dp[ 0 ] 的关系，决定返回值。
class Solution { public: string stoneGameIII(vector<int>& stoneValue) { //初始化 vector<int>dp(stoneValue.size()+3,INT_MIN); int sum=0; dp[stoneValue.size()]=0; dp[stoneValue.size()+1]=0; dp[stoneValue.size()+2]=0; for(int i=stoneValue.size()-1;i>=0;--i){ sum+=stoneValue[i];//统计当前 i 到最后的元素之和 for(int j=1;j<=3;++j){ dp[i]=max(dp[i],sum-dp[i+j]);//找出三种方法中的最大值 } } if(sum-dp[0]==dp[0]) return "Tie"; if(sum-dp[0]>dp[0]) return "Bob"; return "Alice"; } };