1140. 石子游戏 II

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/stone-game-ii/
Star
亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
示例：
输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。
提示：
  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4
通过次数7,214提交次数11,063

法1 动态规划

思路
见古城算法 or 花花酱
记录的是分数差。
notion imagenotion image
本质上是遍历上图所示的树。但是看到有许多重复的状态，所以可以通过记忆化搜索来降低复杂度。
记住每一个子问题，或者残局的解。
状态怎么定义呢？
状态由nums[i:] 和 M的数值决定
dp[i][j] 表示在nums[i:] 中以M=j的方式，先手比后手多得的分数。
  • 当M >= len(nums[i:]) // 2时，此时，先手就可以拿走全部的石头.
因为计算的是先手比后手多拿的分数，所以最后的成绩应该是( sum(piles) + dp[0][1] ) // 2
时间复杂度
题解
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        dp = [[0] * (len(piles)+1) for _ in piles]

        for i in range(len(piles)-1, -1, -1):
            # 遍历  M 
            for j in range(1, len(piles)+1):
                # 能全部取完
                if 2 * j >= len(piles) - i:
                    dp[i][j] = sum(piles[i:])
                else:
                # 不能全部取完，就尽可能的取多
                    dp[i][j] = -float("inf")
                    for x in range(1, 2 * j + 1):
                        cur = sum(piles[i:i+x])
                        # max[x, j] 这是下一轮可以取的 M
                        dp[i][j] = max(dp[i][j], 
                                        cur - dp[i+x][max(x, j)])

        return (sum(piles) + dp[0][1]) // 2
优化版：
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        # dp[i][j] 表示从piles[i:]的石头堆里，
        # 当M = j时, 先手比后手多拿个石头数目
        dp = [[0] * (len(piles)+1) for _ in range(len(piles))]
        sum_ = 0

        # 从 后向前推演
        for i in range(len(dp)-1, -1, -1):
            # 从i开始取，取完的总数量
            sum_ += piles[i]
            
            # 遍历 M
            for j in range(1, len(dp[0])):
                # 说明当前 可以全部取完 剩下的
                if 2*j >= len(dp) - i:
                    dp[i][j] = sum_
                # 不能一次全部取完，那就看看取 几堆可以是的对手之后取的最少
                else:
                    curr = 0
                    best = -float('inf')
                    # 尝试当前 M 对应的所有可能的取的堆数 x 属于 [1, 2M]
                    for x in range(1, 2*j+1):
                        curr += piles[i+x-1]
                        best = max(best, curr - dp[i+x][max(x, j)])
                    dp[i][j] = best

        return (sum(piles) + dp[0][1]) // 2