C++刷LeetCode（1406. 石子游戏 III）【动态规划】

糖逗

题目描述：

1. Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。
   
2. 
   
3. Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。
   
4. 
   
5. 每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。
   
6. 
   
7. 假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，平局（分数相同）返回 "Tie" 。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：values = [1,2,3,7]
    
14. 输出："Bob"
    
15. 解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。
    
16. 示例 2：
    
17. 
    
18. 输入：values = [1,2,3,-9]
    
19. 输出："Alice"
    
20. 解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
    
21. 如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
    
22. 如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
    
23. 注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。
    
24. 示例 3：
    
25. 
    
26. 输入：values = [1,2,3,6]
    
27. 输出："Tie"
    
28. 解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。
    
29. 示例 4：
    
30. 
    
31. 输入：values = [1,2,3,-1,-2,-3,7]
    
32. 输出："Alice"
    
33. 示例 5：
    
34. 
    
35. 输入：values = [-1,-2,-3]
    
36. 输出："Tie"
    
37.  
    
38. 
    
39. 提示：
    
40. 
    
41. 1 <= values.length <= 50000
    
42. -1000&#160;<= values[i] <= 1000
    
43. 
    
44. 来源：力扣（LeetCode）
    
45. 链接：https://leetcode-cn.com/problems/stone-game-iii
    
46. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     string stoneGameIII(vector<int>& stoneValue) {
   
4.         //动态规划
   
5.         int len = stoneValue.size();
   
6.         vector<int>dp(len+1, INT_MIN);//注意此处
   
7.         dp[len] = 0;//注意此处
   
8.         for(int i = len-1; i >= 0; i--){
   
9.             int sum = 0;
   
10.             for(int j = i+1; j <= i+3 && j <= len; j++){//注意此处j <= len
    
11.                 sum += stoneValue[j-1];
    
12.                 dp[i] = max(dp[i], sum - dp[j]);
    
13.             }
    
14.         }
    
15.         if(dp[0] == 0)return "Tie";
    
16.         else if(dp[0] > 0)return "Alice";
    
17.         return "Bob";
    
18.     }
    
19. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -lie-zhi-san-memtx/

糖逗