Leetcode刷题记录 石子游戏专题

感觉一直都久仰minimax大名,但一直没有真正理解这个算法。这也许和我不管是玩棋类游戏还是德策都路边一条也有关系,只能看当前局势和当前最优,往后一步都联想不到。

minimax,一个深度优先的零和博弈树搜索算法,和DP常常一起出现(需要记录树中间节点的状态)

f(i,j)=max(piles[i]−f(i+1,j),piles[j]−f(i,j−1))f(i,j)=max(piles[i]−f(i+1,j), piles[j]−f(i,j−1))

877 Stone Game I

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

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

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

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

区间DP + minimax雏形

from functools import lru_cache
class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        self.piles = piles
        return self.minimax(0, len(self.piles)-1) >= 0
    
    @lru_cache(None)
    def minimax(self, i: int, j: int) -> int:
        if i == j:
            return self.piles[i]
        return max(self.piles[i] - self.minimax(i+1, j), self.piles[j] - self.minimax(i, j-1)) 
        

第一次提交使用了lru_cache,不仅要算哈希还把self也传进去了,不出意外的执行时间路边一条。

lru cache还会导致同一个类实例中更新参数后依然命中旧缓存,因为缓存是挂靠在类函数上的,同一个实例的self不变。当然如果不加self 更加糟糕,新的类实例也会命中旧缓存,一个类的多个实例的函数指向的是同一个函数,但一个函数被多次调用的时候其内部定义的函数是多个该函数的克隆。

就这一问题的解决方案是把整个minimax函数整合进stoneGame中,让每次调用stoneGame的时候创建一个新的minimax函数实例。

from functools import lru_cache
from typing import List

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        @lru_cache(None)
        def minimax(i: int, j: int) -> int:
            if i == j:
                return piles[i]
            return max(piles[i] - minimax(i+1, j),
                       piles[j] - minimax(i, j-1))
        return minimax(0, len(piles)-1) >= 0

当然执行时间还是路边一条。我们需要用到DP,来替换哈希函数。

class Solution:
    def stoneGame(self, piles: list[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]      # 方阵, 只用上三角
        for i in range(n):
            dp[i][i] = piles[i]
        for i in range(n-1):
            for j in range(n-i):
                dp[i][i+j] = max(piles[i]- dp[i+1][i+j], piles[i+j] - dp[i][i+j-1])
        return dp[0][n-1] > 0

执行时间依然逆天–39%

其实这个题它是个脑筋急转弯,本质上先手的人可以保证比后手的人拿到更多的石子。

由于总石子数量为奇数,所以编号为偶数位置的石子和编号为奇数位置的石子的和必有一个更大。

如果Alice开局拿取偶数位置的石子,那么Bob只能拿取奇数位置的石子,后面每一轮都如此。

如果Alice开局拿取奇数位置的石子,那么Bob只能拿取偶数位置的石子,后面没一轮都如此。

所以这是一个先手必胜的游戏。这套论证方法是染色/配对论证。

除此之外,也存在一种显式的双角色博弈树写法,一个例子如下:

def brute(piles):
    @lru_cache(None)
    def dfs(i, j, turn):   # turn=0 Alice(最大化), turn=1 Bob(最小化)
        if i > j:
            return 0
        if turn == 0:
            return max(piles[i] + dfs(i+1, j, 1),
                       piles[j] + dfs(i, j-1, 1))
        return min(dfs(i+1, j, 0),
                   dfs(i, j-1, 0))
    alice = dfs(0, len(piles)-1, 0)
    return 2 * alice > sum(piles)

1140 Stone Game II

Alice 和 Bob 继续他们的石子游戏。许多堆石子 排成一行,每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

Alice 和 Bob 轮流进行,Alice 先开始。最初,M = 1。

在每个玩家的回合中,该玩家可以拿走剩下的 前 X 堆的所有石子,其中 1 <= X <= 2M。然后,令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设 Alice 和 Bob 都发挥出最佳水平,返回 Alice 可以得到的最大数量的石头。

一个显而易见的事情是,除非每次双方都拿一个,不然一次可以拿取的数量显然是越来越多的,因此后续拿取的情况的数量会显而易见的爆炸。

在DP中,一个状态应当包含,现在的首堆石子位置i和M的值。

一个回合可以拿的X数量是min(2*M, n- i),拿了X堆后对手的状态变成了(i + X , max(M, X))

这次不再是只看净得分了,而是需要看Alice最多可以拿取的数量,因此计算方法也需要改变。

最关键的是递推公式,如果f代表一个人从当前状态前可以获得的最大分数,则假如我这回合执行完毕,剩余的后缀和减去对手的f则为我从执行完毕后能获得的最大的分数。因此f(i) = g + S(i + X) - f(i + X)

from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        n = len(piles)
        sum = [0] * (n+1)
        for i in range(1,n+1):
            sum[i] = sum[i-1] + piles[i-1]
        @lru_cache
        def minimax(i:int ,M:int):
            if i >= n:
                return 0
            return max((-sum[i] + sum[n] - minimax(i+X, max(X, M))) 
                       for X in range(1, min(2*M, n-i) + 1) ) 
        return minimax(0,1)

提交后TLE,原因其一是lru_cache没有(None)参数,默认的maxsize=128 不够。

from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        n = len(piles)
        sum = [0] * (n+1)
        for i in range(1,n+1):
            sum[i] = sum[i-1] + piles[i-1]
        @lru_cache(None)
        def minimax(i:int ,M:int):
            if i >= n:
                return 0
            return max((-sum[i] + sum[n] - minimax(i+X, max(X, M))) 
                       for X in range(1, min(2*M, n-i) + 1) ) 
        return minimax(0,1)

但是修改后运行时间依然是仅击败27.54%

from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        n = len(piles)
        sum = [0] * (n+1)
        for i in range(1,n+1):
            sum[i] = sum[i-1] + piles[i-1]
        @lru_cache(None)
        def minimax(i:int ,M:int):
            if i >= n:
                return 0
            if 2*M >= n-i:
                return sum[n] - sum[i]
            return max((-sum[i] + sum[n] - minimax(i+X, max(X, M))) 
                       for X in range(1, min(2*M, n-i) + 1) ) 
        return minimax(0,1)

添加一个剪枝击败48.01%, 将生成器更换为显性循环55.8%

from functools import lru_cache
class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        n = len(piles)
        sum = [0] * (n+1)
        for i in range(1,n+1):
            sum[i] = sum[i-1] + piles[i-1]
        @lru_cache(None)
        def minimax(i, M):
            if i >= n:
                return 0
            if 2*M >= n-i:
                return sum[n] - sum[i]
            best = -1
            for X in range(1, min(2*M, n-i) + 1):
                v = sum[n] - sum[i] - minimax(i+X, max(X, M))
                if v > best:
                    best = v
            return best
        return minimax(0,1)

那就不得不继续问AI怎么在算法上面优化了

答案:滑动窗口最大值+deque 87.08%

from collections import deque
from typing import List

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        pref = [0] * (n + 1)
        for i in range(1, n + 1):
            pref[i] = pref[i-1] + piles[i-1]

        dp = [[0] * (n + 1) for _ in range(n + 1)]
        winM = [deque() for _ in range(n + 1)]   # m1 滑窗, 每个 M 一条
        for M in range(1, n + 1):
            winM[M].append((n, 0))               # 第 n 行全是 0

        for i in range(n - 1, -1, -1):
            S = pref[n] - pref[i]
            dq2 = deque()                        # m2 滑窗
            for M in range(1, n + 1):
                if 2 * M >= n - i:               # 全拿剪枝
                    dp[i][M] = S
                    w = winM[M]
                    while w and w[-1][1] >= S:
                        w.pop()
                    w.append((i, S))             # ★ 剪枝状态也要入队!
                    continue                     # ★ break 改 continue
                cands = (2,) if M == 1 else (2*M - 1, 2*M)
                for X in cands:
                    if X <= n - i:
                        v = dp[i + X][X]
                        while dq2 and dq2[-1][1] >= v:
                            dq2.pop()
                        dq2.append((X, v))
                while dq2 and dq2[0][0] <= M:
                    dq2.popleft()
                m2 = dq2[0][1] if dq2 else float('inf')

                w = winM[M]
                while w and w[0][0] > i + M:
                    w.popleft()
                m1 = w[0][1] if w else float('inf')

                dp[i][M] = S - min(m1, m2)
                while w and w[-1][1] >= dp[i][M]:
                    w.pop()
                w.append((i, dp[i][M]))

        return dp[0][1]

原本的公式为

f[i][M] = g + S(i + X) - f[i + X][max(M,X)] = S(i) - f[i+X][max(M,X)]

可以继续变换成

f[i][M] =S(i) -\min_X dp[i+X][max(M,X)]

假如M > X,因为M不变,所以子状态仅由X决定

f[i][M] =S(i) -\min_X dp[i+X][M]
\min_X dp[i+X][M] = \min_{j \in [i+1,i+M]} dp[j][M]

假如X > M, 这种情况下子状态也仅由X决定

f[i][M] =S(i) -\min_X dp[i+X][X]
\min_X dp[i+X][X] = \min_{X \in [M,2M]} dp[X+i][X]

这两种情况都属于滑动窗口最小值。

这又是一个未解之谜了,等以后遇到这个题目再回来理解吧

1872 Stone Game VIII

Alice 和 Bob 玩一个游戏,两人轮流操作, Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时,如果石子的数目 大于 1 ,他将执行以下操作:

  1. 选择一个整数 x > 1 ,并且 移除 最左边的 x 个石子。
  2. 将 移除 的石子价值之 和 累加到该玩家的分数中。
  3. 将一个 新的石子 放在最左边,且新石子的值为被移除石子值之和。

当只剩下 一个 石子时,游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差,Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ,其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下,Alice 和 Bob 的 分数之差 。

class Solution:
    def stoneGameVIII(self, stones: list[int]) -> int:
        n = len(stones)
        p = [0] * (n+1)
        for i,v in enumerate(stones):
            p[i+1] = p[i] + v
        f = [0] * (n+1)
        best = p[n] - f[n]
        for k in range(n-1,0,-1):
            best = max(best, p[k+1] - f[k+1] )
            f[k] = best
        return f[1]

首先我们留意到场上的总分数和分数分布顺序是永远不变的,所以这还是一个前缀和问题。

p[k]代表前k个石子的价值,也就是我们拿到第k个石子的位置的时候得到的分数

令场上存在的第一个原有石子是第k+1个石子的时候的最优策略为f[k]

在这之后我们能获得的最多分数为p[n] - f[k]

由于p[n]是常数,所以最优策略是f[k]=maxj>k⁡(p[j]−f[j])f[k]=\max_{j>k}(p[j] – f[j])

这个不等式是最关键的,此时第一个原有石子是第k+1个,我们最少拿到第k+1个就够了,因为前面还有一个前缀和石子。

循环中不能直接计算f[0]的值,因为这时没有前缀和石子,必须直接拿两个原有石子。其实f[1]的意义可以理解为拿了一个又按规定放回去了之后的情况,整好符合我们的要求。

Related Posts