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

#724 · #877 · Stone Game(石子游戏)

📌 Problem Statement & Constraints

There is a row of piles with an even number of piles. Alice and Bob alternately take a whole pile from either end, each maximising their own total. Return true if Alice wins; the total is odd, so there is always a winner. Constraints: 2 <= piles.length <= 500, piles.length is even, 1 <= piles[i] <= 500, and sum(piles) is odd.

💡 Core Algorithmic Approaches

  1. dp[i][j] is the best score difference (current player minus opponent) obtainable from the subarray piles[i..j].
  2. Taking the left end gives piles[i] - dp[i+1][j]; taking the right gives piles[j] - dp[i][j-1].
  3. So dp[i][j] is the maximum of the two, and the answer is dp[0][n-1] > 0.
  4. Because the pile count is even and the total is odd, Alice can always force a win, so the function may simply return true.

💻 Benchmark Python3 Implementation

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i + 1][j],
                               piles[j] - dp[i][j - 1])
        return dp[0][n - 1] > 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): every interval is filled once.
💾 Space Complexity
O(n^2), reducible to O(n).

⚠️ Interview Pitfalls & Follow-ups

  • Returning true without justification: it is correct here only because the pile count is even and the total is odd.
  • Tracking two absolute scores: the difference DP is simpler and sufficient.
  • Using piles[i] + dp[i+1][j]: the opponent's turn inverts the sign, so it is a subtraction.
  • Off-by-one in the interval loop: length runs from 2 to n and i up to n - length.
⚡
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