细语呢喃

技术改变生活

0%

leetcode-博弈论

发表于 分类于 ， 阅读次数： 评论数：

本文是leetcode博弈论的题解

https://leetcode.cn/tag/game-theory/problemset/

大部分的知识点是

  • 公平组合博弈(Impartial Combinatorial Games, ICG)
  • MinMax策略：主要是记忆化搜索和动态规划

464. 我能赢吗

两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

示例 1：

1
2
3
4
5
6
7
8
输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2:

1
2
输入：maxChoosableInteger = 10, desiredTotal = 0
输出：true

示例 3:

1
2
输入：maxChoosableInteger = 10, desiredTotal = 1
输出：true

提示:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

状态压缩+记忆化搜索

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
class Solution {
    bool can_win(unordered_map<int, bool>& dp, const int max_v, int state, int remain_v) {
        if (dp.find(state) == dp.end()) {
            bool ans = false;
            for (int i = 1; i <= max_v; ++i) {
                if ((state >> i) & 1) { // used
                    continue;
                }
                if (remain_v - i <= 0 || !can_win(dp, max_v, state | (1 << i), remain_v - i)) {
                    ans = true;
                    break;
                }
            }
            dp[state] = ans;
        }
        return dp[state];
    }

public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        // let dp[state] will win
        unordered_map<int, bool> dp;
        return can_win(dp, maxChoosableInteger, 0, desiredTotal);
    }
};

486. 预测赢家

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

1
2
3
4
5
6
>输入：nums = [1,5,2]
>输出：false
>解释：一开始，玩家 1 可以从 1 和 2 中进行选择。
>如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 
>所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
>因此，玩家 1 永远不会成为赢家，返回 false 。

示例 2：

1
2
3
4
>输入：nums = [1,5,233,7]
>输出：true
>解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
>最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

MinMax算法题，玩家A想要自己分数最大，而对手也想让自己分数最大（相当于让玩家A分数最少）

方法一 MinMax

对于当前玩家：如果选left，之后对手必然让当前玩家的收益最小，则之后能得到的分数就是min(dfs(dp, nums, left + 2, right), dfs(dp, nums, left + 1, right - 1))，选right同理min(dfs(dp, nums, left + 1, right - 1), dfs(dp, nums, left, right - 2));，最后取这两个的max

这里用了记忆化搜索来加速

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int dfs(vector<vector<int>>& dp,
            const vector<int>& nums, 
            int left, int right) {
        if (left > right) return 0;
        if (left == right) return nums[left]; 
        if (dp[left][right] != -1) return dp[left][right];
        int left_v = nums[left] + min(dfs(dp, nums, left + 2, right), dfs(dp, nums, left + 1, right - 1));
        int right_v = nums[right] + min(dfs(dp, nums, left + 1, right - 1), dfs(dp, nums, left, right - 2));
        return dp[left][right] = max(left_v, right_v);
    }

public:
    bool PredictTheWinner(vector<int>& nums) {
        if (nums.empty()) {
            return true;
        }
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), -1));
        int temp = dfs(dp, nums, 0, nums.size() - 1);
        int total = std::accumulate(nums.begin(), nums.end(), 0);
        return temp * 2 >= total;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        if not n & 1: return True
        dp = [[-1 for _ in range(n)] for _ in range(n)]

        def solve(i, j):
            if i < 0 or j < 0 or i >= n or j >= n or i > j: return 0
            if i == j: return nums[i]
            if dp[i][j] < 0:
                dp[i][j] = max(nums[i] + min(solve(i + 2, j), solve(i + 1, j - 1)),
                               nums[j] + min(solve(i + 1, j - 1), solve(i, j - 2)))
            return dp[i][j]

        return (solve(0, n - 1) << 1) >= sum(nums)

方法二

其实就是方法一的改进，

设dp[left][right]表示当前操作玩家在left~right区间内能获得的分数，则有：玩家A每次得到nums[left]或者nums[right]分，然后失去dp[left+1][right]或者dp[left][right-1]分数，最后取左右的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int dfs(vector<vector<int>>& dp,
            const vector<int>& nums, 
            int left, int right) {
        if (left > right) return 0;
        if (dp[left][right] != -1) return dp[left][right];
        int left_v = - dfs(dp, nums, left + 1, right) + nums[left];
        int right_v = - dfs(dp, nums, left, right - 1) + nums[right];
        return dp[left][right] = max(left_v, right_v);
    }

public:
    bool PredictTheWinner(vector<int>& nums) {
        if (nums.empty()) {
            return true;
        }
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), -1));
        int temp = dfs(dp, nums, 0, nums.size() - 1);
        return temp >= 0;
    }
};

改成动态规划版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        if (nums.empty()) {
            return true;
        }
        vector<vector<int>> dp(nums.size() + 1, vector<int>(nums.size(), 0));
        for (int i = nums.size() - 1; i >= 0 ; --i) {
            dp[i][i] = nums[i];
            for (int j = i + 1; j < nums.size(); ++j) {
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][nums.size() - 1] >= 0;
    }
};

877. 石子游戏

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

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

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

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

示例 1：

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

示例 2：

1
2
输入：piles = [3,7,2,3]
输出：true

和486题一样，多了两个条件

  1. 和为奇数，没有平局
  2. 石头为偶数个

方法一

同486题

方法二

先手必胜，由于石头为偶数个，必然可以根据下标分为两组，如6个石头的情况：

1
2
0 2 4
 1 3 5

假设奇数组的和更大（1， 3， 5）那可以选5，则下一次对手只能从偶数里选：

1
2
0 2 4
 1 3

无论对手选什么，我们都能选奇数组（1或则3）

因此，先手只需要提前算好奇数组还是偶数组的和大即可

1
2
3
4
5
6
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

810. 黑板异或游戏

黑板上写着一个非负整数数组 nums[i] 。

Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。

并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0 ，这个玩家获胜。

假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

  • 当前数字异或和为0，根据题意，必然先手胜

  • 当剩余为偶数的时候，而当前的数字异或不为0，则先手必胜

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool xorGame(vector<int>& nums) {
        if (!(nums.size() & 1)) return true;
        int xor_sum = 0;
        for (int num : nums) {
            xor_sum ^= num;
        }
        return xor_sum == 0;
    }
};
请我喝杯咖啡吧~