1
class Solution:
2
    def stoneGameII(self, piles: List[int]) -> int:
3
        n = len(piles)
4
        dp = {}
5

6
        def recursion(index, M):
7
            # if we reached to the end we cannot score any value
8
            if index == n:
9
                return 0
10
            # we search if we have solved the same case earlier
11
            if (index, M) in dp:
12
                return dp[(index, M)]
13
            # total remaining score is the sum of array from index to the end
14
            total = sum(piles[index:])
15
            # if we can take the complete array it is the best choice
16
            if index + 2 * M >= n:
17
                return total
18
            # my_score is the score we are getting as the player who is playing
19
            my_score = 0
20
            for x in range(index, index + 2 * M):
21
                # opponent score will be calculated by next recursion
22
                opponent_score = recursion(x + 1, max(M, x - index + 1))
23
                # my_score is the remaining value of total - opponent_score
24
                my_score = max(my_score, total - opponent_score)
25
            # this is memoization part
26
            dp[(index, M)] = my_score
27
            # return the score
28
            return my_score
29

30
        return recursion(0, 1)