[leetcode] 1140 stone game II

Alice and Bob continue their stone game . Many heaps of stones Line up , Every pile has a whole number of stones piles[i]. Who has the most stones to decide the outcome of the game .

Alice and Bob take turns , Alice starts first . first ,M = 1.

In each player's turn , The player can take the rest front X All the stones in the pile , among 1 <= X <= 2M. then , Make M = max(M, X).

The game continued until all the stones were taken away .

Suppose Alice and Bob are at their best , Return to the maximum number of stones Alice can get .

Example 1：

Input ： piles = [2,7,9,4,4]
Output ： 10
explain ： If at first Alice Took a pile ,Bob Took two piles , then Alice Take two more piles . Alice can get 2 + 4 + 4 = 10 Pile up . If Alice At first, I took away two piles , that Bob You can take away the remaining three piles . under these circumstances ,Alice obtain 2 + 7 = 9 Pile up . return 10, Because it's bigger .

Example 2:

Input ： piles = [1,2,3,4,5,100]
Output ： 104

Tips ：

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

Ideas

dp[M][i] Indicates that the remaining stone pile is piles[i : len] when ,M = M Under the circumstances , The maximum number of stones a first mover can get

• i + 2M >= length, dp[M][i] = sum(piles[i : length]), The remaining piles can be taken away directly
• i + 2M < length, dp[M][i] = max(dp[M][i],sum(piles[i : length]) - dp[max(M, X)][i + X]), among 1 <= X <= 2M, You can't take all the remaining piles away , Then the best situation is to let the next person take less . For all at this time x Value , The next person from X Start picking up ,M Turn into max(M, X), So the next person can take dp[max(M, X)][i + X], The best thing you can do is sum[i : len - 1] - dp[max(M, X)][i + X]

# Dynamic programming 
class Solution(object):
    def stoneGameII(self, piles):
        length = len(piles)
        mysum = 0
        dp = [[0 for i in range(length)] for j in range(length+1)]
        
        for i in range(length-1,-1,-1):
            mysum += piles[i]
            for M in range(1,length+1):
                if i+2*M>=length:
                    dp[M][i]=mysum
                else:
                    for X in range(1,2*M+1):
                        dp[M][i] = max(dp[M][i],mysum-dp[max(M,X)][i+X])
        return dp[0][1]

Reference article ：https://leetcode.cn/problems/stone-game-ii/solution/java-dong-tai-gui-hua-qing-xi-yi-dong-17xing-by-lg/