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

(77) 2024-05-23 15:01:01

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];
}
};

想法:

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

THE END

发表回复