< Back




1406. Stone Game III

Like all dynamic programming problem, we got two solutions we can discuss. I attempted the recursive
solution at first, however, I tracked more states than necessary and overcomplicated the solution.
Let's think about this dynamic programming problem, our states are:

  * Index of the current stone
  * Score of Alice
  * Score of Bob
  * Player choosing a stone

Our recurrence relation is:

  * We can make three choices during each turn:
    * Select 1 stone
    * Select 2 stones
    * Select 3 stones

We recursively assess all three choices, and maximize our choice for an outcome wherein the current
player's score is the highest. We're essentially creating a game-playing AI, however, keeping track
of whose turn it is, and the score for each player adds an unnecessary amount of dimensions.

What we realize is, whoever wins or loses, is based on the difference of their scores. If the
difference is 0, Alice and Bob have tied. If the difference is positive, Alice wins, and vice versa
for Bob.

We don't need to keep track of which player is playing, our solution works if we maximize the
difference during our turn for our selection of stones versus the next player's selection. Thus, we
eliminate the states that keep track of Alice's and Bob's score into a single variable, and we also
eliminate the need for turn tracking.

For the iterative, tabular solution, we only need to maintain 4 cells in a 1D array - we only need
to know the outcome of the three previous player choices in order to solve T[i]. The bottom-up
approach starts solving from the last stone and works backwards, but the recurrence relation is
still the same. We select 1 to 3 stones and maximize this sum against the difference of the
previously completed turns.

The recursive solutions is as follows:


  class Solution:
      def stoneGameIII(self, stoneValue: List[int]) -> str:
          n = len(stoneValue)

          @cache
          def dp(i: int) -> int:
              if i == n:
                  return 0

              return max(
                  sum(stoneValue[i:j]) - dp(j) for j in range(i + 1, min(i + 3, n) + 1)
              )

          diff = dp(0)
          return "Alice" if diff > 0 else ("Bob" if diff < 0 else "Tie")


_ Time Complexity:

  O(n) - Where n is the number of stones, we iterate through each stone once.

_ Space Complexity:

  O(n) - We recursively evaluate the input n times, causing our stack frames to reach this size.


The iterative, tabular solution is as follows:


  class Solution:
      def stoneGameIII(self, stoneValue: List[int]) -> str:
          n, T = len(stoneValue), [0] * 4

          for i in range(n - 1, -1, -1):
              T[i % 4] = max(
                  sum(stoneValue[i:j]) - T[j % 4] for j in range(i + 1, min(i + 3, n) + 1)
              )

          return "Alice" if T[0] > 0 else ("Bob" if T[0] < 0 else "Tie")


_ Time Complexity:

  O(n) - We iterate through the input n times.

_ Space Complexity:

  O(1) - We use constant space for our memoization table.