Stone Game II

Stone Game II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Interval DP subpattern.

Problem statement

You are given piles, where piles[i] is the number of stones in the i-th pile from left to right. Two players take turns, and all piles must be taken in their original order: on a turn, a player removes a consecutive prefix of the remaining piles.

Maintain a value M, initially 1. On a turn, the player must take between 1 and 2 M piles, or all remaining piles if fewer are available. After taking X piles, the next turn uses M = max(M, X).

Both players choose moves optimally. Return the greatest number of stones the first player can collect, assuming the second player also plays optimally.

Example 1:

Input: piles = [2] Output: 2 Explanation: The first player can take the only pile, collecting all 2 stones.

Example 2:

Input: piles = [1,2,3] Output: 3 Explanation: If the first player takes 1 pile, the second player can take the remaining two piles and collect 5 stones. If the first player takes 2 piles, the second player takes the last pile, so the first player's best result is 3.

Example 3:

Input: piles = [3,1,10,2] Output: 5 Explanation: Taking the first pile gives the first player 3 stones, and optimal subsequent play allows them to collect the final pile as well, for a total of 5.

Constraints:

- 1 <= piles.length <= 100 - 1 <= piles[i] <= 10^4 - Every element of piles is an integer - piles represents the piles in their fixed left-to-right order

Topics and companies

Topics: Array, Dynamic Programming, Memoization, Recursion.

How to practise Stone Game II on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^3), where n is piles.size(). There are O(n^2) states, and each state considers O(n) possible moves. time and O(n^2) for the memoization table, plus O(n) for suffix sums and recursion stack. space.

Open Stone Game II in the code editor, or read the Stone Game II editorial for a worked solution with its approach and complexity analysis.

Where Stone Game II sits in the DSA pattern sheet

Problems related to Stone Game II

Other problems that use the same Interval DP and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.