⚡Flashcard Drill➔
NeetCode #725LC-1140Medium2-D Dynamic ProgrammingNC 250
← Back to All Problems

#725 · #1140 · Stone Game II(石子游戏 II)

📌 Problem Statement & Constraints

Alice and Bob take turns taking piles from the front of piles. On a turn a player takes X piles with 1 <= X <= 2M, then M becomes max(M, X), with M starting at 1. Each player maximises their own total. Return the maximum number of stones Alice can get. Constraints: 1 <= piles.length <= 100, 1 <= piles[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. dp[i][m] is the maximum stones the current player can collect from piles[i..] when the current M equals m.
  2. Taking x piles yields suffix[i] - suffix[i+x] immediately, and the opponent then faces dp[i+x][max(m, x)].
  3. So dp[i][m] = max over x of (suffix[i] - suffix[i+x] - dp[i+x][max(m, x)]).
  4. The state space is O(n^2) because M never needs to exceed n.

💻 Benchmark Python3 Implementation

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        suffix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + piles[i]
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for m in range(1, n + 1):
                for x in range(1, 2 * m + 1):
                    if i + x > n:
                        break
                    nxt_m = min(n, max(m, x))
                    gain = suffix[i] - suffix[i + x] - dp[i + x][nxt_m]
                    dp[i][m] = max(dp[i][m], gain)
        return dp[0][1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^3): O(n^2) states, each with up to O(n) transitions, bounded by n <= 100.
💾 Space Complexity
O(n^2): the DP table.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to update M: the next state uses max(M, X), the larger of the old M and the piles just taken.
  • Letting M exceed n: clamp max(m, x) to n to stay in bounds.
  • Using prefix instead of suffix sums: the remaining piles from i onward are needed.
  • Returning suffix[0] - dp[0][1]: dp[0][1] is already Alice's share as the first player.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems