C++刷LeetCode（1140. 石子游戏 II）【动态规划】【博弈】
题目描述：亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles。游戏以谁手中的石子最多来决出胜负。
亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
示例：
输入：piles =
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。
提示：
1 <= piles.length <= 100
1 <= piles <= 10 ^ 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stone-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int stoneGameII(vector<int>& piles) {
int len = piles.size();
int sum = 0;
vector<vector<int> >dp(len, vector<int>(len + 1, 0));
for(int i = len - 1; i >= 0; i--){
sum += piles;
for(int j = 1; j <= len; j++){
if(i + 2 * j >= len){
dp = sum;
}else{
for(int k = 1; k <= 2 * j; k++){
dp = max(dp, sum - dp);
}
}
}
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/stone-game-ii/solution/java-dong-tai-gui-hua-qing-xi-yi-dong-17xing-by-lg/ {:10_312:}
页:
[1]