LC 2029. 石子游戏 IX

https://leetcode-cn.com/problems/stone-game-ix/

这题我估计看题解肯定也是看不懂，所以这题还是自己想办法。这题最简单的办法还是模拟，但是状态肯定很大，理论上是N[0] * N[1] * N[2]这么多个状态。但是有几个特点，可以让我们对状态进行化简：

  1. N[0] 也就是 x%3=0 这个状态，其实只需要保存0/1即可。因为如果Alice拿一个0, Bob也可以拿一个0, 这样状态其实就和原来完全一致而不会有任何变化。所以最终只有一个人会使用0进行一次翻转。
  2. 如果一开始Alice拿2，那么Bob肯定拿2，接着Alice拿1，然后Bob继续拿2，如此往复。可以写成2 - (2-1) - (2-1) 。。。 所以每个1-2对其实是可以消除的。
  3. 但是也不是完全消除，为了进入某个状态，可以至少保留一个1或者是2。

这样下来：

这种博弈搜索的算法很少写，总结一下就是几乎不需要考虑是alice还是bob拿。虽然我代码里面有 `ab` 这个参数，这个参数是为了知道最后一次清空的时候是谁，但是其他min/max部分是没有考虑ab参数的。 

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        cnt = [0] * 3
        for x in stones:
            cnt[x % 3] += 1
        cnt[0] %= 2

        mx = max(0, min(cnt[1], cnt[2]) - 1)
        cnt[1] -= mx
        cnt[2] -= mx

        def search(t, cnt, ab):
            if sum(cnt) == 0:
                # if this is alice, then lose
                # else win.
                return ab

            values = [1]
            for i in range(3):
                if (i + t) % 3 == 0: continue
                if cnt[i] > 0:
                    cnt2 = cnt.copy()
                    cnt2[i] -= 1
                    x = search(t + i, cnt2, 1 - ab)
                    values.append(x)

            m = min(values)
            return 1 - m

        ans = search(0, cnt, 0)
        return ans == 1