博弈论取石子问题_博弈论实验报告总结

lc877：

题目：

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

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

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

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

示例：

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

提示：

2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles) 是奇数。

代码：

方法一：找到动态规划递归关系，然后使用括号类型的动态规划方法去做；

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int len=piles.size();
    vector<vector<int>> record(len,vector<int>(len,0));
    for(int i=1;i<=len;i++){
        for(int l=0;l<len-i+1;l++){
            int r=l+i-1;
            if(l==r){
                record[l][r]=piles[l];
            }else{
                record[l][r]=max(piles[r]-record[l][r-1],piles[l]-record[l+1][r]);
            }
        }
    }
    return record[0][len-1]>0?true:false;
    }
};

思路：将谁输谁赢的问题，转化为分数差的问题；

方法二：——将二维数组转化为一维问题：

思路：

public stoneGame(vector<int>& piles){
    int length=piles.size();
    auto dp=vector<int>(length);
    for(int i=0;i<length;i++){
        for(int j=i+1;j<length;j++){
            dp[j]=max(piles[i]-dp[j],piles[j]-dp[j-1]);
}
}
    return dp[length-1]>0;
}

分析状态转移方程可以看到，dp[i][j]的值只和dp[i+1][j]与dp[i][j-1]有关，即在计算dp的第i行的值的时候，只需要使用到dp的第i行和第i+1行的值，因此可以使用一维数组代替二维数组，对空间进行优化；

lc1140：

题目：

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

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

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

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

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

示例：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stone-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

（递归方法）

class Solution {
public:
    vector<vector<int>> record;
    int tranverse(vector<int>& piles,int start,int end,int M){
     if(record[start][M-1]!=-1)return record[start][M-1];
     int res=-1000000,sum=0;
    if(end-start+1<=2*M){
        for(int i=start;i<=end;i++){
            sum+=piles[i];
        }
        record[start][M-1]=sum;
        return sum;
    }
    else{
        bool a=false;
        for(int i=start;i<start+2*M;i++){
            sum+=piles[i];
            int t=sum-tranverse(piles,i+1,end,max(i-start+1,M));
            res=max(res,t);
            a=true;
        }
        record[start][M-1]=res;
        return res;
    }
}
int stoneGameII(vector<int>& piles) {
    record.resize(piles.size(),vector<int>(piles.size(),-1));
    int cha= tranverse(piles,0,piles.size()-1,1);
    int sum=0;
    for(int i=0;i<piles.size();i++){
        sum+=piles[i];
    }
    return int((sum+cha)/2);
}

};

想法：该方法使用动态规划的话，可能思路不是很直接，那么可以使用递归方法，传统暴力的递归方法可能会导致超时，那么选择记忆化搜索就不会超时；

lc 1406:

题目：

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

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

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

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

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

提示：

1 <= values.length <= 50000
-1000 <= values[i] <= 1000

代码：

class Solution {
public:
    vector<int> record;

int tranverse(int current,vector<int>& stoneValue){

    if(stoneValue.size()-1==current){
        return stoneValue[current];
    }
    if(stoneValue.size()<=current)return 0;
    if(record[current]!=-1){
        return record[current];
    }
    int sum=0,cha=INT_MIN;
    
    for(int i=0;i<min(3,int(stoneValue.size())-current);i++){
        sum+=stoneValue[i+current];
        cha=max(cha,sum-tranverse(current+i+1,stoneValue));
    }
    record[current]=cha;
    return cha;
}

string stoneGameIII(vector<int>& stoneValue) {
    int len=stoneValue.size();
    record.resize(len,-1);
    int cha=INT_MIN,sum=0;
    for(int i=0;i<min(len,3);i++){
        sum+=stoneValue[i];
        cha=max(cha,sum-tranverse(i+1,stoneValue));
    }
    if(cha>0)return "Alice";
    else if(cha==0)return "Tie";
    else return "Bob";
}
};

想法：

每一个value值有可能是负数，所以需要不要到最后区间的时候统计加起来返回，而是应该判断最后一个；方法还是传统的递归方法+记忆化搜索。

lc 1510:

题目：

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。

示例 1：

输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：

输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：

输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：

输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：

输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。

代码：

方法一——记忆化搜索：

vector<int> r;

bool tranverse(int n){

    if(r[n]!=-1)return bool(r[n]);
    if(n==0){
        r[n]=false;
        return false;};
    bool lx= false;
    for(int i=1;i<=int(sqrt(n));i++){
        lx|= !tranverse(n-i*i);
    }
    r[n]=lx;
    return lx;
}

bool winnerSquareGame(int n) {
    r.resize(n+1,-1);
    return tranverse(n);
}

方法二——动态规划：

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k * k <= i; ++k) {
                if (!f[i - k * k]) {
                    f[i] = true;
                    break;
                }
            }
        }
        
        return f[n];
    }
};

想法：f[i]表示n=1时A先手最优策略下胜还是负；所以只要找到一种激活成功教程办法，就能保证true；自行理解；

lc 1563:

题目：

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。
示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28
示例 3：

输入：stoneValue = [4]
输出：0

提示：

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6

代码：

方法一——动态规划（超时）：

class Solution {
public:
    int stoneGameV(vector<int>& stoneValue) {
        int len=stoneValue.size();
    vector<vector<int>> v(len, vector<int>(len,-1));
    vector<int> sum(len+1,0);
    for(int i=1;i<=len;i++){
        sum[i]=sum[i-1]+stoneValue[i-1];
    }
    for(int i=1;i<=len;i++){
        for(int l=0;l<len-i+1;l++){
            int r=l+i-1;
            if(l==r)v[l][r]=0;
            else if(l+1==r){
                v[l][r]=min(stoneValue[l],stoneValue[r]);
            }
            else{
                for(int k=l;k<r;k++){
                    int sum1=sum[k+1]-sum[l];
                    int sum2=sum[r+1]-sum[k+1];
                    int temp=0;
                    if(sum1>sum2){
                        temp=sum2+v[k+1][r];
                    }else if(sum1==sum2){
                        temp=sum1+max(v[k+1][r],v[l][k]);
                    }else{
                        temp=sum1+v[l][k];
                    }
                    v[l][r]=max(v[l][r],temp);
                }
            }
        }
    }

    return v[0][len-1];
    }
};

思路：分解拿石子问题为矩阵形状的动态规划问题。从len=1的开始递归，借助sum数组，获取d[i,j]内可以拿到的最大值，而d[i,j]内可以拿到的最大值又依赖于他其中的所有d[i,k],d[k+1,j]等等，建立递归关系；不要忘记当两部分相等的时候可以由Alice来选择，这个时候需要注意，这是第三种，情况，需要假如if-else语句中考虑；

方法二——优化方法一：

代码：

const int N = 505;
int s[N][N], g[N][N], f[N][N], mxl[N][N], mxr[N][N];
class Solution {
public:
    int stoneGameV(vector<int> &a) {
        int n = a.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j] = g[i][j] = s[i][j] = 0;
                mxl[i][j] = mxr[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            s[i][i] = a[i];
            g[i][i] = i;
            for (int j = i + 1; j < n; j++) {
                s[i][j] = s[i][j - 1] + a[j];
                int now = g[i][j - 1];
                while (s[i][j] - s[i][now] > s[i][now]) {
                    now++;
                }
                g[i][j] = now;
            }
        }

        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                int mid = g[l][r];
                int ls = s[l][mid];
                int rs = s[mid + 1][r];
                if (ls == rs) {
                    f[l][r] = max(f[l][r], mxl[l][mid]);
                    f[l][r] = max(f[l][r], mxr[mid + 1][r]);
                } else {
                    if (mid > l) {
                        f[l][r] = max(f[l][r], mxl[l][mid - 1]);
                    }
                    if (mid < r) {
                        f[l][r] = max(f[l][r], mxr[mid + 1][r]);
                    }
                }
                int v = f[l][r] + s[l][r];
                if (l == r) {
                    mxl[l][r] = mxr[l][r] = v;
                } else {
                    mxl[l][r] = max(v, mxl[l][r - 1]);
                    mxr[l][r] = max(v, mxr[l + 1][r]);
                }
            }
        }
        return f[0][n - 1];
    }
};

思路：核心在于把区间中的那个临界中间值提前找好，这样可以减少一次循环，把O(n^3)的时间复杂度降为O(n^2)。

lc 1686:

题目：

Alice 和 Bob 轮流玩一个游戏，Alice 先手。

一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。

给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。

所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。

请你推断游戏的结果，用如下的方式表示：

如果 Alice 赢，返回 1 。
如果 Bob 赢，返回 -1 。
如果游戏平局，返回 0 。

示例 1：

输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。
示例 2：

输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。
示例 3：

输入：aliceValues = [2,4,3], bobValues = [1,6,7]
输出：-1
解释：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。

提示：

n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100

代码：

class Solution {
public:
    
int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
    int len=aliceValues.size();
    vector<int> index;
    vector<int> sums;
    for(int i=0;i<len;i++){
        sums.push_back(aliceValues[i]+bobValues[i]);
        index.push_back(i);
    }
    sort(index.begin(),index.end(), [&sums](size_t index_1, size_t index_2) { return sums[index_1] > sums[index_2];});

    int cha=0;
    bool flag=true;
    for(int i=0;i<len;i++){
        if(flag){cha+=aliceValues[index[i]];}
        else{
            cha-=bobValues[index[i]];
        }
        flag=!flag;
    }

    if(cha>0)return 1;
    else if(cha==0)return 0;
    else return -1;
}

};

思路：

需要找出其中的贪心关系，优先选择alice[i]+bob[i]大的，因为这样的话，表示自己拿的大的程度同时拿走了别人拿到大的的机会，大概就是这样；

lc 1690:

题目：

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。
示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

提示：

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

代码：

方法一——递归（不加引用超时，加引用不超时）：

class Solution {
public:
    vector<vector<int>> record;

int tranverse(vector<int>&stones, int start, int end,int sum){
    if(record[start][end]!=-1)return record[start][end];
    if(start==end){
        record[start][end]=0;
        return 0;
    }
    if(start+1==end){
        record[start][end]=max(stones[start],stones[end]);
        return record[start][end];
    }

    record[start][end]=max(sum-stones[start]-tranverse(stones,start+1,end,sum-stones[start]),sum-stones[end]- tranverse(stones,start,end-1,sum-stones[end]));

    return record[start][end];
}
int stoneGameVII(vector<int>& stones) {
    int len=stones.size();
    record.resize(len,vector<int>(len,-1));
    int sum=0;
    for(int i=0;i<len;i++){
        sum+=stones[i];
    }

    int res=tranverse(stones,0,len-1,sum);
    return res;
}
};

方法二——（动态规划）:

class Solution {
public:
    
int stoneGameVII(vector<int>& stones) {
    int len=stones.size();
    vector<vector<int>> record(len,vector<int>(len,-1));
    vector<int> sum(len+1,0);
    for(int i=1;i<=len;i++){
        sum[i]=sum[i-1]+stones[i-1];
    }

    for(int i=1;i<=len;i++){
        for(int l=0;l<len-i+1;l++){
            int r=l+i-1;
            if(l==r){
                record[l][r]=0;
            }else if(l+1==r){
                record[l][r]=max(stones[l], stones[r]);
            }else{
                record[l][r]=max(sum[r+1]-sum[l+1]-record[l+1][r],sum[r]-sum[l]-record[l][r-1]);
            }
        }
    }

    return record[0][len-1];
}
};

想法：

一般情况来讲，动态规划会比递归快一些；