Solution Explanation for LeetCode 1140: Stone Game II

This problem involves a two-player game with piles of stones. The players take turns removing stones, and the goal is to maximize the number of stones collected. The key to solving this efficiently is recognizing the optimal strategy involves dynamic programming.

Understanding the Game:

Each turn, a player can take 1 to 2M stones from the beginning of the remaining piles, where M is the maximum number of piles taken in any previous turn. M starts at 1. The game ends when all stones are taken.

Approach: Dynamic Programming with Memoization

The most efficient approach uses dynamic programming with memoization to avoid redundant calculations. We'll create a recursive function dfs(i, m) that represents the maximum number of stones the current player can get, starting from index i in the piles array and with the current maximum number of piles taken (M) being m.

1. Base Case:

If m * 2 >= n - i, it means there are few enough remaining piles that the current player can take them all. In this case, the current player takes all remaining stones (s[n] - s[i], where s is the prefix sum array).

2. Recursive Step:

Otherwise, the current player can choose to take x piles (1 ≤ x ≤ 2m). For each choice of x, the opponent will get the maximum number of stones they can obtain from the remaining piles, which is recursively calculated as dfs(i + x, max(m, x)). The current player aims to maximize their score, so they choose the x that minimizes the opponent's score, leading to the maximum score for themselves.

3. Memoization:

To avoid recomputing the same dfs(i, m) values repeatedly, we use memoization (a cache) to store previously computed results.

4. Prefix Sum:

We use a prefix sum array s to efficiently calculate the sum of stones in a range. s[i] stores the sum of the first i piles. The sum of stones from index i to j is then s[j+1] - s[i].

Time and Space Complexity:

• Time Complexity: O(n^3). The recursive function dfs has three nested loops implicitly: the outer loop is the recursion depth (n), the inner loop iterates through possible values of x (2m), and inside the min function is a nested loop (implicit in the recursion).
• Space Complexity: O(n^2). This is due to the memoization table, which stores results for dfs(i,m) for all possible values of i and m.

Code Implementation (Python):

from functools import cache
from itertools import accumulate
import math
 
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        s = list(accumulate(piles, initial=0))  # Prefix sum array
 
        @cache
        def dfs(i: int, m: int = 1) -> int:
            if m * 2 >= n - i:  # Base case: Take all remaining piles
                return s[n] - s[i]
            
            min_opponent_score = float('inf')
            for x in range(1, min(2 * m + 1, n - i)): # Optimization: Limit x to available piles
                min_opponent_score = min(min_opponent_score, dfs(i + x, max(m, x)))
            return s[n] - s[i] - min_opponent_score  # Maximize current player's score
 
        return dfs(0)

Other Languages:

The approach and logic remain the same across different programming languages. The key differences lie in syntax and the way memoization is implemented (using dictionaries/maps in Python/Java/C++, or similar data structures in other languages). The Python code above is already efficient and well-structured. Adapting it to other languages involves straightforward translation. The earlier response already contains code samples in several languages, you can refer to those.