[数据结构与算法]【LeetCode】1140-石子游戏II

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

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

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

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

假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。

示例 1：

输入： piles = [2,7,9,4,4]
输出： 10
解释： 如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。

示例 2:

输入： piles = [1,2,3,4,5,100]
输出： 104

提示：

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

思路

dp[M][i]表示剩余石子堆为piles[i : len]时，M = M的情况下，先取的人能获得的最多石子数

• i + 2M >= length, dp[M][i] = sum(piles[i : length])，剩下的堆数能够直接全部取走
• i + 2M < length, dp[M][i] = max(dp[M][i]，sum(piles[i : length]) - dp[max(M, X)][i + X]), 其中 1 <= X <= 2M，剩下的堆数不能全部取走，那么最优情况就是让下一个人取的更少。对于此时所有的x取值，下一个人从X开始取起，M变为max(M, X)，所以下一个人能取dp[max(M, X)][i + X]，此事最多能取sum[i : len - 1] - dp[max(M, X)][i + X]

#动态规划
class Solution(object):
    def stoneGameII(self, piles):
        length = len(piles)
        mysum = 0
        dp = [[0 for i in range(length)] for j in range(length+1)]
        
        for i in range(length-1,-1,-1):
            mysum += piles[i]
            for M in range(1,length+1):
                if i+2*M>=length:
                    dp[M][i]=mysum
                else:
                    for X in range(1,2*M+1):
                        dp[M][i] = max(dp[M][i],mysum-dp[max(M,X)][i+X])
        return dp[0][1]

参考文章：https://leetcode.cn/problems/stone-game-ii/solution/java-dong-tai-gui-hua-qing-xi-yi-dong-17xing-by-lg/