博弈论算法优化

MrHe··3 min read

有一堆石子，共 n 个。你和另一个人轮流从堆里拿石子，每次可以拿 1 个、2 个或 3 个。拿到最后一个石子的人算赢。假设你先手，并且两个人都足够聪明，请问你是否能赢？

这种“两个人足够聪明”的题，就是典型的博弈论。所谓“足够聪明”，意思就是每个人在轮到自己时，都会选择最优策略，绝不失误。

解法一：暴力递归，一力降十会

一看到这题，我的第一反应通常是：我能不能赢，取决于我走了某一步之后，对方是不是必输。

这是博弈论的核心思想：我赢，当且仅当我能走到一个让对手必输的局面。

这句话有点套娃的感觉，但它天然就指向了递归。

我们来定义一个函数 canIWin(n)，表示当前剩下 n 个石子，轮到我，我是否能赢。

根据规则，我可以拿 1、2 或 3 个石子：

  1. 如果我拿 1 个，剩下 n-1 个石子就轮到对手了。如果对手在剩下 n-1 个石子的情况下是“必输”的，那我就赢了。对手“必输”，等价于 canIWin(n-1) 返回 false。

  2. 如果我拿 2 个，剩下 n-2 个石子。如果 canIWin(n-2) 返回 false，我也赢了。

  3. 如果我拿 3 个，剩下 n-3 个石子。如果 canIWin(n-3) 返回 false，我还是赢了。

只要这三种选择中，有一种能让对手陷入必输局面，我就能赢。

这么一来，思路就清晰了。

canIWin(n) 为 true 的条件是：!canIWin(n-1) 或者 !canIWin(n-2) 或者 !canIWin(n-3)。

当然，还得有递归的出口（base case）：

  • n = 1, 2, 3：我直接全拿走，必赢。

  • n <= 0：这种情况其实轮不到我拿，说明上一个人已经拿完了，所以我输了。

代码写出来就是这样：

// 解法一：暴力递归
public boolean canWin(int n) {
    if (n <= 0) {
        return false; // 没石子了，我输了
    }
    // Base case: 我可以直接拿完
    if (n >= 1 && n <= 3) {
        return true;
    }

    // 我尝试拿1, 2, 3个石子，看看有没有一种情况能让对手输
    // 我拿1个，对手面对n-1个。如果对手输了(!canWin(n-1))，我就赢了
    boolean opponentLoses1 = !canWin(n - 1);
    // 我拿2个，对手面对n-2个。
    boolean opponentLoses2 = !canWin(n - 2);
    // 我拿3个，对手面对n-3个。
    boolean opponentLoses3 = !canWin(n - 3);

    // 只要有一种情况对手输，我就赢了
    return opponentLoses1 || opponentLoses2 || opponentLoses3;
}

这个解法很直观，但只要你拿个稍微大点的 n（比如 50）去跑一下，就会发现它慢得离谱。为什么？因为有大量的重复计算。比如算 canWin(10)，会去算 canWin(9), canWin(8), canWin(7)。而算 canWin(9) 又会去算 canWin(8), canWin(7), canWin(6)。你看，canWin(8) 和 canWin(7) 就被重复算了。

这是典型的递归通病，下一步自然就想到了优化：记忆化搜索或者说动态规划。

解法二：动态规划，空间换时间

既然暴力递归有重复计算，那我们就搞个缓存，把计算过的结果存起来。下次再遇到同样的情况，直接从缓存里拿，不用再算了。

这就是从“暴力递归”到“记忆化搜索”的转变，也是动态规划思想的雏形。

我们可以创建一个 dp 数组，dp[i] 用来存剩下 i 个石子时，先手方是否能赢。

  • dp[i] = true: 表示剩下 i 个石子，先手必赢。

  • dp[i] = false: 表示剩下 i 个石子，先手必输。

我们可以从 i=1 开始，一步步往上填这个 dp 表。

  • dp[1] = true: 我直接拿1个，赢。

  • dp[2] = true: 我直接拿2个，赢。

  • dp[3] = true: 我直接拿3个，赢。

  • dp[4] 怎么算？我能走到 i=3, i=2, i=1 的局面。而 dp[3], dp[2], dp[1] 都是 true，意味着我无论怎么走，都把一个“必胜”的局面留给了对手。所以我必输。dp[4] = false。

  • dp[5] 怎么算？我可以选择拿 1 个石子，剩下 4 个。局面交给对手，而 dp[4] 是 false（对手必输）。太好了，我赢定了。所以 dp[5] = true。

状态转移方程呼之欲出： dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3]

这个方程跟我们递归的逻辑一模一样。

// 解法二：动态规划
public boolean canWinDP(int n) {
    if (n <= 0) {
        return false;
    }
    if (n <= 3) {
        return true;
    }

    // dp[i] 表示剩下 i 个石子时，当前玩家是否能赢
    boolean[] dp = new boolean[n + 1];

    // base cases
    dp[1] = true;
    dp[2] = true;
    dp[3] = true;

    for (int i = 4; i <= n; i++) {
        // 如果我走完一步，能让对手陷入dp值为false（必输）的局面，我就赢了
        dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
    }

    return dp[n];
}

这个解法的时间复杂度是 O(N)，空间复杂度也是 O(N)。相比于指数级的暴力递归，已经是质的飞跃了。

但是，这就到头了吗？对于一个算法博主来说，肯定要继续往下挖。O(N) 还是有点慢，有没有 O(1) 的解法？

解法三：数学规律，大道至简

当一个问题能用 DP 解决，并且状态转移只依赖于前面几个固定的状态时，这里面通常隐藏着数学规律。

我们把 dp 数组的结果打印出来看看：

  • dp[1] = true

  • dp[2] = true

  • dp[3] = true

  • dp[4] = false (因为前面1,2,3都是true)

  • dp[5] = true (因为可以走到dp[4]这个false状态)

  • dp[6] = true (可以走到dp[4])

  • dp[7] = true (可以走到dp[4])

  • dp[8] = false (因为前面5,6,7都是true)

规律是不是出来了？ Win, Win, Win, Lose, Win, Win, Win, Lose, ...

这是一个以 4 为周期的循环。只要石子数量 n 是 4 的倍数，先手就必输。否则，先手必赢。

为什么是 4？

因为每次可以拿 m=1, 2, 3 个石子。我作为先手，如果 n 不是 m+1（也就是 4）的倍数，我总有办法拿掉 k 个石子，使得剩下的 n-k 是 4 的倍数。

  • 如果 n % 4 = 1，我就拿 1 个，剩下 n-1，是 4 的倍数。

  • 如果 n % 4 = 2，我就拿 2 个，剩下 n-2，是 4 的倍数。

  • 如果 n % 4 = 3，我就拿 3 个，剩下 n-3，是 4 的倍数。

我把一个“4的倍数”这个棘手的“必输局面”扔给了对手。对手无论拿 1、2、3 个，剩下的都不再是 4 的倍数。下一轮，我又可以把局面调整回“4的倍数”扔给他。

如此往复，最后剩下 4 个石子的时候，轮到他。他怎么拿，我都能拿到最后一个。

所以，判断胜负的关键，就是看 n 是不是 4 的倍数。

// 解法三：数学规律
public boolean canWinMath(int n) {
    return n % 4 != 0;
}

代码简单到令人发指。时间复杂度和空间复杂度都是 O(1)。

总结一下

从一个简单的博弈问题，我们经历了三种思维层次：

  1. 暴力递归：最符合人类直觉的思考方式，定义好状态和选择，直接开干。这是解决问题的基础。

  2. 动态规划：在暴力递归的基础上，发现重复计算问题，通过加缓存（空间换时间）进行优化。这是从“能解决”到“高效解决”的跨越。

  3. 数学规律：通过小样本数据，观察 DP 表的结果，大胆猜测，小心验证，最终发现问题的数学本质。这是从“编码”到“洞察”的升华。

  • #5y2a5byi6k66