看似小游戏，其实是博弈论：聊聊 Flip Game II 背后的算法思维

看似小游戏，其实是博弈论：聊聊 Flip Game II 背后的算法思维

作者：Echo_Wish

很多算法题都有一个特点：
表面看起来像小游戏，背后其实是博弈论。

今天我们聊一个非常经典的题目：

Flip Game II（翻转游戏 II）

题目很简单：

给定一个字符串，只包含+和-，
每次操作可以把连续两个++变成--。

例如：

++++

玩家可以这样操作：

++++ → --++ ++++ → +--+ ++++ → ++--

两个玩家轮流操作，谁不能操作谁输。

问题是：

给定初始字符串，先手玩家能不能赢？

第一次看到这个题，很多人会觉得这不就是个模拟题吗？

但当字符串稍微长一点，你就会发现事情没那么简单。

因为：

每一步选择都会影响后续局势。

这其实就是一个典型的博弈搜索问题。