Method 1: minimax + memory
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
#TC: O(n^2)
#SC: O(n^2)
#The recursive function helper takes input of left and right points of piles.
#Assume the player A starts picking stone within left and right points of piles.
#The output is the (stone obtained by A - stone obtained by B) (B is the other player)
#Then it becomes a combination problem with time complexity O(2^n). To reduce complexity, use a
#dict to record the situation that is already solved. Then the time complexity becomes O(n^2)
n = len(piles)
dp = {} #key: tuple(start, end), value: number of stones that one who start first can get than the other.
def helper(start, end):
if (start, end) in dp:
return dp[(start, end)]
if (start == end):
dp[(start, start)] = piles[start]
return piles[start]
left = piles[start] - helper(start+1, end)
right = piles[end] - helper(start, end-1)
dp[(start, end)] = max(left, right)
return max(left, right)
return helper(0, n-1) > 0
Method 2: dynamic programming
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
#TC: O(n^2)
#SC: O(n^2)
#memory is defined the same as Minimax method.
n = len(piles)
memory = {}
for start in range(n-1, -1, -1):
for end in range(start, n):
if start == end:
memory[(start, end)] = piles[start]
else:
left = piles[start] + memory[(start+1, end)]
right = piles[end] + memory[(start, end-1)]
memory[(start, end)] = max(left, right)
return memory[(0, n-1)] > 0
Method 2.5: reduced space version from method 2.
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
#TC: O(n^2)
#SC: O(n)
n = len(piles)
memory = {}
for start in range(n-1, -1, -1):
for end in range(start, n):
if start == end:
memory[start] = piles[start]
previous = piles[start]
else:
left = piles[start] + memory[start+1]
right = piles[end] + previous
previous = max(left, right)
memory[start] = max(left, right)
return memory[0] > 0