算法之 博弈问题

算法之 博弈问题

博弈问题在算法和编程领域中占据重要地位，涉及双方之间的策略对抗。本文将深入探讨几种常见的博弈类型，包括巴什博弈、尼姆博弈和斐波那契博弈等，并通过具体的算法题目来解释这些博弈问题的解法。

巴什博弈

巴什博弈是一种经典的博弈问题，通常涉及双方轮流取物，每次取的数量有限制，最后取完者获胜。下面通过一个具体的算法题目来说明巴什博弈的解法。

292. Nim 游戏

这道题目实际上是一个典型的巴什博弈问题。分析问题结束的情况，当最后轮到一方的时候，剩余的石头的数目达到1、2、3的时候，该方就是赢的，否则就是输的。那么怎么才能保证这种情况？我们可以观察到，通过n%4,就可以知道最后是否可以剩下对应的1、2、3个数目的石头。

class Solution:
    def canWinNim(self, n: int) -> bool:
        # 由于每个人都是最优解，所以只要查看n是不是4的倍数即可
        if n % 4 == 0:
            return False
        else:
            return True

尼姆博弈

尼姆博弈是一种更复杂的博弈类型，通常涉及多堆物品，双方轮流取物，每次可以从任意一堆中取任意数量的物品，最后取完者获胜。尼姆博弈的解法通常涉及异或运算。

斐波那契博弈

斐波那契博弈是一种基于斐波那契数列的博弈问题，通常涉及双方轮流取物，每次取的数量必须是斐波那契数列中的数，最后取完者获胜。

其他博弈

除了上述几种常见的博弈类型外，还有一些其他的博弈问题，例如除数博弈。

1025. 除数博弈

这道题目是一个典型的除数博弈问题。分析问题结束的情况，当最后轮到一方的时候，剩余的石头的数目达到1、2、3的时候，该方就是赢的，否则就是输的。那么怎么才能保证这种情况？我们可以观察到，通过n%4,就可以知道最后是否可以剩下对应的1、2、3个数目的石头。

class Solution:
    def divisorGame(self, n: int) -> bool:
        # win = {2}
        # los = {1}
        dp = [False] * (n + 1)
        if n == 1:
            return False
        dp[1] = False
        dp[2] = True
        for i in range(3, n + 1):
            flag = 0
            for j in range(1, i):
                if i % j == 0:
                    if (i - j) in los:
                        flag = 1
                        break
            if flag:
                dp[i] = True
                win.add(i)
            else:
                los.add(i)
        return dp[n]