Alex and Lee 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.
Alex and Lee take turns, with Alex 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 Alex and Lee play optimally, return the maximum number of stones Alex can get.
Keyword: DP
For the piles array, suppose Alex and Lee are at the position i, and Alex need to make his best move now in order to get more stones. Suppose f(x, M) means the best move made at position x, we have the equation that f(i, M) = min[sum - f(x) for x in range(i + 1, i + 2 * M)], as both sides need to make their best move.
It’s obvious that the complexity would be high and we need a cache to reduce time/space cost. Here we use a dictionary to do so, but a better way would be using lrucache, which is a decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls.
class Solution(object):
def stoneGameII(self, piles):
"""
:type piles: List[int]
:rtype: int
"""
length = len(piles)
if length <= 2: return sum(piles)
record = [0 for i in range(length)]
record[-1] = piles[-1]
for i in range(length - 2, -1, -1):
record[i] = piles[i] + record[i + 1] # sum of all piles start from position i
cache = {} # use cache to reduce time cost
def optimalCanTake(pos, M):
# the `f` we mentioned above
if (pos, M) in cache:
return cache[(pos, M)]
if pos >= length:
return 0
if 2 * M >= length - pos:
return record[pos]
nextMinValue = 999999999
for i in range(pos + 1, pos + 2 * M + 1):
# i is X
nextMinValue = min(nextMinValue, optimalCanTake(i, max(M, i - pos)))
result = record[pos] - nextMinValue
cache[(pos, M)] = result
return result
return optimalCanTake(0, 1)