# Leetcode Contest 147

#### Stone Game II

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)``````