难度: Medium
原题连接
内容描述
Alex and Lee play a game with piles of stones. There are an even 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. The total number of stones is odd, so there are no ties.
Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.
Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.
Example 1:
Input: [5,3,4,5]
Output: true
Explanation:
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.
Note:
2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******
记忆化搜索，beats 8.70%
from functools import lru_cache
class Solution:
def stoneGame(self, piles):
"""
:type piles: List[int]
:rtype: bool
"""
@lru_cache(None)
def helper(i, j): # 在这个区间内，第一个拿的人能得到的最多的stone
if j - i == 1:
return max(piles[i:j+1])
return max(sum(piles[i:j+1]) - helper(i+1, j), sum(piles[i:j+1]) - helper(i, j-1))
first = helper(1, len(piles)-1) # alex 取第一个
second = helper(0, len(piles)-2) # alex 取最后一个
if first < sum(piles) / 2 or second < sum(piles):
return True
return False我们发现我们在helper函数里面一直会调用sumRange，所以用个前缀和数组记录一下，省的每次都算浪费时间
果然快多了，beats 43.48%
from functools import lru_cache
class Solution:
def stoneGame(self, piles):
"""
:type piles: List[int]
:rtype: bool
"""
prefix = [0]
for i, num in enumerate(piles):
prefix.append(prefix[i-1] + num)
@lru_cache(None)
def helper(i, j): # 在这个区间内，第一个拿的人能得到的最多的stone
if j - i == 1:
return max(piles[i:j+1])
tmp = prefix[j+1] - prefix[i]
return max(tmp - helper(i+1, j), tmp - helper(i, j-1))
first = helper(1, len(piles)-1) # alex 取第一个
second = helper(0, len(piles)-2) # alex 取最后一个
if first < prefix[-1] / 2 or second < prefix[-1]:
return True
return False思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******
DP, dp[i][j]代表在piles[i:j+1]区间中，第一个拿的人能得到的最多的stone
beats 52.17%
class Solution:
def stoneGame(self, piles):
"""
:type piles: List[int]
:rtype: bool
"""
dp = [[0] * len(piles) for i in range(len(piles))]
for i in range(len(piles)):
dp[i][i] = piles[i]
for i in range(len(piles)-1):
for j in range(1, len(piles)):
dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
return dp[0][-1] > 0进一步优化时间, beats 65.22%
class Solution:
def stoneGame(self, piles):
"""
:type piles: List[int]
:rtype: bool
"""
dp = [[0] * len(piles) for i in range(len(piles))]
for i in range(len(piles)):
dp[i][i] = piles[i]
for i in range(1, len(piles)):
for j in range(len(piles) - i):
dp[j][j + i] = max(piles[j] - dp[j + 1][j + i], piles[j + i] - dp[j][j + i - 1])
return dp[0][-1] > 0思路 3 - 时间复杂度: O(1)- 空间复杂度: O(1)******
因为sum(piles)是奇数
所以有两种可能
- sum(piles[0:len(piles):2] > sum(piles[1:len(piles):2]
- sum(piles[1:len(piles):2] > sum(piles[0:len(piles):2]
因为alex先选，我们发现如果他愿意的话，他可以选到所有的偶数index pile，也可以选到所有的奇数index pile，所以他永远可以赢
class Solution:
def stoneGame(self, piles):
"""
:type piles: List[int]
:rtype: bool
"""
return True