Keshawn_lu's Blog

Leetcode 1140. 石子游戏 II

动态规划
字数统计: 591阅读时长: 2 min
2023/02/22 Share

题目简介：

爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

示例 1：

1
2
3
输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。

提示：

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10^4

思路：

我们用dp[i][j]来代表剩余[i : pile.size() - 1]堆时，M = j时，当前取的人能获得的最多石子数

分为以下两种情况：

  1. 当2 * M >= piles.size() - 1时，说明当前的人能取走剩余的所有石子，因此dp[i][M] = sum，即剩余的石子数总和。
  2. 当2 * M < piles.size() - 1时，说明无法取走剩下的所有石子，因此我们需要枚举下一个人可能会取走的石子堆数x，减去以后，从而得到当前的人所能取得的最大石子数，因此dp[i][M] = max(dp[i][M], sum - dp[i + x][max(M, x)]) (1 <= x <= 2 * M)。

最后返回dp[0][1]即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int stoneGameII(vector<int>& piles) {

        vector<vector<int>> dp(piles.size(), vector<int>(piles.size() + 1));

        int sum = 0;
        for(int i = piles.size() - 1; i >= 0; i--){ //剩余 [i : pile.size() - 1]堆

            sum += piles[i];

            for(int M = 1; M <= piles.size(); M++){ //取M堆

                if(2 * M >= piles.size() - i){  //能全部取走

                    dp[i][M] = sum;
                }

                else{

                    for(int x = 1; x <= 2 * M; x++){

                        dp[i][M] = max(dp[i][M], sum - dp[i + x][max(M, x)]);   //减去下一个人能拿走的石子
                    }
                }
            }
        }

        return dp[0][1];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网