[leetcode] 1140. Stone Game II

[leetcode] 1140. Stone Game II

Description

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Example 1:

Input: piles = [2,7,9,4,4]Output: 10Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Example 2:

Input: piles = [1,2,3,4,5,100]Output: 104

Constraints:

1 <= piles.length <= 1001 <= piles[i] <= 104

分析

题目的意思是：两个人拿石子的游戏，Alice首先开始拿，M初始化为1，在每个玩家的回合中，该玩家可以拿走剩下的前X堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。一直持续到所有的石子都被拿走。这道题用dp，我分享一下别人的思路：

dp[i][j]表示当前位于第i个位置且M为j时，先手能取到的最大的石子数量。需要从后往前遍历，因为最后的状态都可以直接得到。维护后缀求和数组sums有效位置的下标从0到n-1，M的下标从1到n，初始化：对于所有的1<=j<=n, f(n,j)=0，这是边界递推时需要枚举这一次先手取多少个石子k，满足1<=k<=2*j,且i+k<=n

dp[i][j]=max(dp[i][j],sum[i]-dp[i+k][max(j,k)])

最后答案是dp[0][1],表示当前在第0个位置，且M为1时先手能取到的最大值。

代码

class Solution: def stoneGameII(self, piles: List[int]) -> int: n=len(piles) sums=[0]*(n+1) dp=[[0]*(n+1) for i in range(n+1)] for i in range(n-1,-1,-1): sums[i]=sums[i+1]+piles[i] for i in range(n-1,-1,-1): for j in range(1,n+1): for k in range(1,2*j+1): if(i+k<=n): dp[i][j]=max(dp[i][j],sums[i]-dp[i+k][max(j,k)]) return dp[0][1]

参考文献

​​[LeetCode] LeetCode 1140. Stone Game II​​​​[Java] 动态规划 清晰易懂17行 演示​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。