JZX轻语：简
LeetCode 1140 - 石子游戏II
发表于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)