333. Stone Game III

HardDynamic Programming

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 the 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 player with the highest score wins the game. The game could end in a draw. Assume Alice and Bob **play optimally**. Return `"Alice"` if Alice will win, `"Bob"` if Bob will win, or `"Tie"` if they will end the game with the same score.

Examples

Input: [1,2,3,7]

Output: Bob

Explanation: dp[0] = -1 < 0. Whatever Alice takes from the front, Bob is left with a stronger remainder, so Bob wins.

Constraints

  • 1 <= stoneValue.length <= 5 * 10^4
  • -1000 <= stoneValue[i] <= 1000
Loading...

Run checks all cases above. Submit evaluates all test cases.