Alice and Bob continue their games with piles of stones. There are several stones **arranged in a row**, and each stone has an associated value which is an integer given in the array `stoneValue`

.

Alice and Bob take turns, with **Alice** starting first. On each player’s turn, that player can take **1, 2 or 3 stones** from the **first** remaining stones in the row.

The score of each player is the sum of values of the stones taken. The score of each player is **0** initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob **play optimally**.

Return *“Alice”* if Alice will win, *“Bob”* if Bob will win or *“Tie”* if they end the game with the same score.

**Example 1:**

Input:values = [1,2,3,7]Output:"Bob"Explanation:Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

**Example 2:**

Input:values = [1,2,3,-9]Output:"Alice"Explanation:Alice must choose all the three piles at the first move to win and leave Bob with negative score. If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. The next move Alice will take the pile with value = -9 and lose. If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. The next move Alice will take the pile with value = -9 and also lose. Remember that both play optimally so here Alice will choose the scenario that makes her win.

**Example 3:**

Input:values = [1,2,3,6]Output:"Tie"Explanation:Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

**Example 4:**

Input:values = [1,2,3,-1,-2,-3,7]Output:"Alice"

**Example 5:**

Input:values = [-1,-2,-3]Output:"Tie"

**Constraints:**

`1 <= values.length <= 50000`

`-1000 <= values[i] <= 1000`

**Solution: DP with memorization**

dp(i) := max relative score the current player can get if start the game from the i-th stone.

dp(i) = max(sum(values[i:i+k]) – dp(i + k)) 1 <= k <= 3

Time complexity: O(n)

Space complexity: O(n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: string stoneGameIII(vector<int>& stoneValue) { const int n = stoneValue.size(); vector<int> mem(n, INT_MIN); // Maximum `relative score` the current player can achieve // if start from the i-th stone. function<int(int)> dp = [&](int i) { if (i >= n) return 0; // end of game. if (mem[i] != INT_MIN) return mem[i]; for (int j = 0, s = 0; j < 3 && i + j < n; ++j) { s += stoneValue[i + j]; // s - dp(.) to get `relative score`. mem[i] = max(mem[i], s - dp(i + j + 1)); } return mem[i]; }; const int score = dp(0); return score > 0 ? "Alice" : (score == 0 ? "Tie" : "Bob"); } }; |

## Python3

1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua class Solution: def stoneGameIII(self, stoneValue: List[int]) -> str: n = len(stoneValue) stoneValue += [0, 0, 0] dp = [-10**9] * n + [0, 0, 0] for i in range(n - 1, -1, -1): for k in (1, 2, 3): dp[i] = max(dp[i], sum(stoneValue[i:i+k]) - dp[i+k]) return "Alice" if dp[0] > 0 else "Bob" if dp[0] < 0 else "Tie" |