C++刷LeetCode（1140. 石子游戏 II）【动态规划】【博弈】

糖逗

题目描述：

1. 亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
   
2. 
   
3. 亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
   
4. 
   
5. 在每个玩家的回合中，该玩家可以拿走剩下的&#160;前&#160;X&#160;堆的所有石子，其中&#160;1 <= X <= 2M。然后，令&#160;M = max(M, X)。
   
6. 
   
7. 游戏一直持续到所有石子都被拿走。
   
8. 
   
9. 假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
   
10. 
    
11. &#160;
    
12. 
    
13. 示例：
    
14. 
    
15. 输入：piles = [2,7,9,4,4]
    
16. 输出：10
    
17. 解释：
    
18. 如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
    
19. 如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
    
20. 所以我们返回更大的 10。
    
21. &#160;
    
22. 
    
23. 提示：
    
24. 
    
25. 1 <= piles.length <= 100
    
26. 1 <= piles[i]&#160;<= 10 ^ 4
    
27. 
    
28. 来源：力扣（LeetCode）
    
29. 链接：https://leetcode-cn.com/problems/stone-game-ii
    
30. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int stoneGameII(vector<int>& piles) {
   
4.         int len = piles.size();
   
5.         int sum = 0;
   
6.         vector<vector<int> >dp(len, vector<int>(len + 1, 0));
   
7.         for(int i = len - 1; i >= 0; i--){
   
8.             sum += piles[i];
   
9.             for(int j = 1; j <= len; j++){
   
10.                 if(i + 2 * j >= len){
    
11.                     dp[i][j] = sum;
    
12.                 }else{
    
13.                     for(int k = 1; k <= 2 * j; k++){
    
14.                         dp[i][j] = max(dp[i][j], sum - dp[i+k][max(k, j)]);
    
15.                     }
    
16.                 }
    
17.             }
    
18.         }
    
19.         return dp[0][1];
    
20.     }
    
21. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -dong-17xing-by-lg/

糖逗