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
dp[i][m]is the maximum stones the current player can collect frompiles[i..]when the currentMequalsm.- Taking
xpiles yieldssuffix[i] - suffix[i+x]immediately, and the opponent then facesdp[i+x][max(m, x)]. - So
dp[i][m] = max over x of (suffix[i] - suffix[i+x] - dp[i+x][max(m, x)]). - The state space is O(n^2) because
Mnever needs to exceedn.
💻 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 usesmax(M, X), the larger of the oldMand the piles just taken. - Letting
Mexceedn: clampmax(m, x)tonto stay in bounds. - Using prefix instead of suffix sums: the remaining piles from
ionward 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.