Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 1140 Stone Game II - Problem Statement

LeetCode 1140

Piles of stones in a row. Players alternate taking XX piles from the front, where 1X2M1 \leq X \leq 2M. After taking, MM becomes max(M,X)\max(M, X). Initially M=1M = 1. Both play optimally.

What's the max stones Player 1 can get? Example: piles =[2,7,9,4,4]= [2, 7, 9, 4, 4], M=1M = 1. Player 1 can take 11 or 22 piles. Taking 22 gives 2+7=92 + 7 = 9 stones and sets M=2M = 2. Now Player 2 can take 11 to 44 piles... The variable MM adds a new dimension to the state. This problem combines interval-style thinking with an extra parameter.