发表于 2024.06.23

• 零和博弈中极小化极大算法的应用。我们寻求的是Alice的最大优势分数，可以将其作为递归函数的返回值，然后通过记忆化搜索来优化递归过程。在Alice层的递归中，我们尽可能的让Alice的分数最大化，而在Bob层的递归中，我们尽可能的让Alice的分数最小化。这样，我们就可以得到Alice至少能获得的分数(即如果双方都采取最优的策略，Alice的分数)。

  from functools import lru_cache
  
  
  class Solution:
      def stoneGameII(self, piles: List[int]) -> int:
          @lru_cache(None)
          def dp(begin: int, m: int, is_max: bool):
              if begin == len(piles):
                  return 0
              if is_max:
                  # Alice的回合，尽可能的让Alice的分数最大化
                  return max(
                      sum(piles[begin: begin + x]) + dp(begin + x, max(m, x), False)
                      for x in range(1, min(len(piles) - begin, 2 * m) + 1)
                  )
              else:
                  # Bob的回合，尽可能的让Alice的分数最小化
                  return min(
                      dp(begin + x, max(m, x), True)
                      for x in range(1, min(len(piles) - begin, 2 * m) + 1)
                  )
  
          return dp(0, 1, True)

  频繁地区间求和操作会使得时间复杂度增加，我们可以通过前缀和来优化这一过程。

  from functools import lru_cache
  
  
  class Solution:
      def stoneGameII(self, piles: List[int]) -> int:
          prev_sum = [0] * len(piles)
          for i, pile in enumerate(piles):
              prev_sum[i] = (prev_sum[i - 1] if i > 0 else 0) + pile
  
          @lru_cache(None)
          def dp(begin: int, m: int, is_max: bool):
              if begin == len(piles):
                  return 0
              last_prev_sum = prev_sum[begin - 1] if begin > 0 else 0
              if is_max:
                  return max(
                      prev_sum[begin + x - 1] - last_prev_sum + dp(begin + x, max(m, x), False)
                      for x in range(1, min(len(piles) - begin, 2 * m) + 1)
                  )
              else:
                  return min(
                      dp(begin + x, max(m, x), True)
                      for x in range(1, min(len(piles) - begin, 2 * m) + 1)
                  )
  
          return dp(0, 1, True)

• LC 题目链接