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
dp[i][j]is the best score difference (current player minus opponent) obtainable from the subarraypiles[i..j].- Taking the left end gives
piles[i] - dp[i+1][j]; taking the right givespiles[j] - dp[i][j-1]. - So
dp[i][j]is the maximum of the two, and the answer isdp[0][n-1] > 0. - 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
truewithout 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:
lengthruns from 2 tonandiup ton - length.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.