【动态规划】博弈论：取石子游戏合集

博弈论的本质是在最坏的情况下做最好的选择。

LeetCode 877. 石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正整数颗石子，数目为 piles[i] 。

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

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

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

 

 

1140. 石子游戏 II

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

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

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

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

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

 

 代码：

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
    int n=piles.size();
    vector<vector<int>>f(n+2,vector<int>(n+1));
    vector<int>s(n+1);
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+piles[i-1];
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
              for(int k=1;i+k-1<=n&&k<=2*j;k++){
                  f[i][j]=max(f[i][j],s[n]-s[i-1]-f[i+k][max(k,j)]);
              }
        }
    }
    return f[1][1];
    }
};

LeetCode1406. 石子游戏 III 

Alice 和 Bob 用几堆石子在做游戏。

几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。

在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。

比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

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

 sum用前缀和预处理

class Solution {
public:
//f[i]表示i~n中先手的最高得分
//f[i]可以有3中选择s[i],s[i]+s[i+1],s[i]+s[i+1]+s[i+2];
//对应后手的最高得分是f[i+1],f[i+2],f[i+3]
//可以用总分sum(i~n)减去对手的得分得到先手的得分
//所以可以得到递推式:f[i]=max(f[i],sum(i~n)-f[i+k]),k=1,2,3且i+k-1<=n
//初始化f[n+1]=0
    int sum[50005];
    int dp[50005];
    string stoneGameIII(vector<int>& stoneValue) {
int n=stoneValue.size();

   sum[0]=0;
   for(int i=1;i<=n;i++){
       sum[i]=sum[i-1]+stoneValue[i-1];
   }
   dp[n+1]=0;
   for(int i=1;i<=n;i++){
       dp[i]=-0x3f3f3f3f;
   }
   for(int i=n;i>=1;i--){
       for(int j=1;j<=3&&i+j-1<=n;j++){
           dp[i]=max(dp[i],sum[n]-sum[i-1]-dp[i+j]);
       }
   }
   int a=dp[1];
   int b=sum[n]-a;

   if(a>b){
       return "Alice";
   }else if(a==b){
       return "Tie";
   }else{
       return "Bob";
   }
    }
};

ACwing取石子1321：

Alice 和 Bob 两个好朋友又开始玩取石子了。

游戏开始时，有 N 堆石子排成一排，然后他们轮流操作（Alice 先手），每次操作时从下面的规则中任选一个：

1. 从某堆石子中取走一个；
2. 合并任意两堆石子。

不能操作的人 输。

Alice 想知道，她是否能有必胜策略。

 

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 55, M = 50050;
int f[N][M];
int dp(int a, int b)
{
    int &v = f[a][b];
    if (v != -1) return v;
    //如果a=0，v是奇数先手必胜，v是偶数，先手必败
    if (!a) return v = b % 2;
    //如果b变为1，那么b会归到a中
    if (b == 1) return dp(a + 1, 0);
    //从a中取1个石子，要判断a是否为0
    if (a && !dp(a - 1, b)) return v = 1;
    //从b中取一个石子，要判断b是否为0
    if (b && !dp(a, b - 1)) return v = 1;
     //合并a中两堆，如果b中没有堆，那么a合并后加入b中，b多了两个操作
     //如果b中有堆，那么合并a后b中多了三个操作
    if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return v = 1;
    //从a中取一堆b中取一堆合并，要判断ab是否为0
    if (a && b && !dp(a - 1, b + 1)) return v = 1;
    //如果以上情况都不能必胜，那么返回0
    return v = 0;
}

int main()
{
    memset(f, -1, sizeof f);

    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int n;
        scanf("%d", &n);
        int a = 0, b = 0;
        for (int i = 0; i < n; i ++ )
        {
            int x;
            scanf("%d", &x);
            if (x == 1) a ++ ;
            else b += b ? x + 1 : x;
        }

        if (dp(a, b)) puts("YES");
        else puts("NO");
    }

    return 0;
}

ACwing取石子游戏1322：

在研究过 Nim 游戏及各种变种之后，Orez 又发现了一种全新的取石子游戏，这个游戏是这样的：

有 n堆石子，将这 n堆石子摆成一排。

游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。

Orez 问：对于任意给出的一个初始局面，是否存在先手必胜策略。

题解看不懂。