0%

leetcode石子游戏专题 van♂游戏

发表于 分类于 ， 评论次数:：
本文字数： 4.4k 阅读时长 ≈ 4 分钟

leetcode 877 石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

1
2
3
4
5
6
7
8
9
10
示例：

输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

思路：典型的区间dp,根据区间长度划分状态，f[i][j]表示取完了除i-j区间之后玩家可得最高分数,如果当前轮到A那么应当在取区间首尾中的最大值，否则只能得到首尾中的最小值。当前轮到谁可以这样确定，因为每轮只能取一次，所以每次剩下的石堆数量要么是奇数，要么是偶数，所以可以根据这个特性来判断是谁取数。
有动态转移方程：轮到自己时$dp[i][j]=max(dp[i+1][j]+nums[i],dp[i][j-1]+nums[j]);$
轮到对方时，$dp[i][j]=min(dp[i+1][j],dp[i][j-1];$
最后判断先手玩家得分是否大于另一个玩家。
时间复杂度: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool stoneGame(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>>f(n,vector<int>(n,0));
        if(n & 1)for(int i=0;i<n;i++)f[i][i] = nums[i];
        
        for(int i = 2 ; i<=n; i++){//枚举区间长度
            for(int j = 0;j+i-1<n;j++){//f[i][j]表示取完了除i-j区间之后 玩家可得最高分数
                int l = j, r = i+j-1;
                if((n-(r-l+1))%2==0)f[l][r] = max(f[l+1][r] + nums[l],f[l][r-1]+nums[r]);
                else f[l][r] = min(f[l+1][r],f[l][r-1]);
            }
        }
        int sum = 0;
        for(auto i=0;i<n;i++)sum+=nums[i];
        if(f[0][n-1]>=sum-f[0][n-1])return true;
        else return false; 
    }
};

leetcode 1140 石子游戏 II

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

亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。

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

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

假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

1
2
3
4
5
6
7
8
示例：

输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。

思路：只能理解记忆化搜索的思路，没理解dp的思路。memo[i][j]表示从下标i开始取数时,取x(1<=x<=j)堆石子能得到的最多的石子数。所以显然可以记忆化搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int presum[101];
    unordered_map<int,unordered_map<int,int>>memo;
    int n;
    int stoneGameII(vector<int>& piles) {
        n = piles.size();
        for(int i=1;i<=n;i++)presum[i]=presum[i-1]+piles[i-1];
        return dfs(piles,0,1);
    }
    int dfs( vector<int>& piles,int start,int m){
        if(memo.find(start)!=memo.end() && memo[start].find(m)!=memo[start].end())return memo[start][m];
        if(start>=n)return 0;
        int max_stone=0;
        for(int i=1;i<=2*m;i++){
            int nm = max(i,m);
            int next_max=dfs(piles,start+i,nm);//对方取得的最大石子数
            //利用前缀和更新自己能获得的最大石子数
            max_stone = max(max_stone,presum[n] - presum[start]-next_max);
        }
        memo[start][m]=max_stone;
        return max_stone;
    }
};

leetcode 1406 石子游戏 III

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” ，Bob 赢了就返回 “Bob”，平局（分数相同）返回 “Tie” 。

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
示例 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"

思路：f[i]表示从下标i开始取数，先手比后手多的分数。

  1. 初始值，f(n)=0，其余待定。
  2. 转移时，对于 f(i) 有三种决策，取第 i 堆，取第 i 和 i+1 堆，以及取第 i，i+1 和 i+2 堆，对应的转移分别为 $max(s(i)−f(i+1),s(i)+s(i+1)−f(i+2),s(i)+s(i+1)+s(i+2)−f(i+3)$。
  3. 最终，如果 f(0)=0，则平局；如果 f(0)>0 则 Alice 胜，否则 Bob 胜。
    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
    class Solution {
    public:
        string stoneGameIII(vector<int>& stoneValue) {
            int n = stoneValue.size();
            vector<int> f(n + 1);

            f[n] = 0;

            for (int i = n - 1; i >= 0; i--) {
                f[i] = stoneValue[i] - f[i + 1];
                if (i < n - 1)
                    f[i] = max(f[i], stoneValue[i] + stoneValue[i + 1] - f[i + 2]);

                if (i < n - 2)
                    f[i] = max(f[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] 
                                        - f[i + 3]);
            }

            if (f[0] == 0)
                return "Tie";
            else if (f[0] > 0)
                return "Alice";
            else return "Bob";
        }
    };