区间动态规划例题：石子游戏 II（两人轮流从数组开头或结尾取石子，但每次可以取1到2M堆石子，M为当前可取堆数上限，取完最后一堆的玩家获胜，假设两人都发挥最佳水平，问先手是否能赢）

问题描述
给定一个整数数组 piles，piles[i] 表示第 i 堆石子的数量。两名玩家轮流进行，从数组的最左侧开始取石子（即只能从剩余数组的开头取石子），每次可以取走1 到 2M 堆石子（M 是当前轮次允许取的最大堆数，初始 M = 1）。取走的石子总数加入该玩家的得分。游戏结束后，得分最高的玩家获胜。假设两位玩家都发挥最佳水平，如果先手玩家能赢，返回 true，否则返回 false。

例子
输入：piles = [2,7,9,4,4]
输出：true
解释：先手玩家第一步取前 2 堆（M=1，可取 1 到 2 堆），得到 2+7=9 分，剩余 [9,4,4]，M 更新为 2。之后无论后手如何取，先手都能获胜。

问题理解
这是一个博弈类区间DP问题，但取石子只能从左侧连续取，因此状态定义通常用一维DP表示从某个位置开始的游戏结果。不过，由于 M 会随取走的堆数增加，我们仍需用区间DP思想考虑“剩余数组”的状态。状态需包含当前起始位置和当前 M 值。

解题思路

1. 定义状态
   dp[i][m] 表示当剩余石子堆为 piles[i...n-1]（i 从 0 到 n-1），当前 M 值为 m 时，先手玩家能比后手玩家多得的分数（即“先手得分 - 后手得分”）。
   注意：m 可能会变大，最大为 n（因为最多一次取完所有堆），但实际 m 不会超过 n，可优化。

2. 状态转移
   当前先手可以选择取走 x 堆石子（1 ≤ x ≤ 2m），取走 piles[i] + ... + piles[i+x-1] 的分数，然后剩余石子从 i+x 开始，M 更新为 max(m, x)，此时轮到后手变为新局面的“先手”。
   因此，转移方程为：

   dp[i][m] = max( sum(i, i+x-1) - dp[i+x][max(m, x)] )  for x in 1..2m
   

   其中 sum(i, j) 表示 piles[i] + ... + piles[j] 的和。
   这个公式的含义：先手取 x 堆得到 sum，之后后手在剩余局面中会尽力最大化自己的领先分数（即 dp[i+x][...] 表示剩余局面中“新先手”的领先分数），所以先手本次操作的净领先分数是 sum - dp[i+x][...]，先手会选择最大值。

3. 初始化与计算顺序

   • 当 i == n 时，没有石子，dp[n][m] = 0。
   • 计算顺序：i 从 n-1 递减到 0，m 从大到小或从小到大均可，但需注意 m 可能大于 n-i，可限制 m 最大为 n（因为一次最多取完）。
   • 为了快速求子数组和，可预处理前缀和数组 prefix，sum(i, j) = prefix[j+1] - prefix[i]。

4. 最终答案
   先判断 dp[0][1] 是否 > 0。如果大于 0，表示先手领先（即先手总分高于后手），先手能赢。

逐步推导示例（piles = [2,7,9,4,4]）

1. 预处理前缀和：[0, 2, 9, 18, 22, 26]。
2. n=5，设 dp[5][m]=0。
3. 计算 i=4（最后一堆）：
   • m=1：可取 1 或 2 堆，但只剩 1 堆，只能取 x=1，sum=4，dp[4][1] = 4 - dp[5][max(1,1)] = 4 - 0 = 4。
   • m≥2 时类似，dp[4][m] = 4。
4. 计算 i=3（堆[4,4]）：
   • m=1：可取 1 或 2 堆。
     • x=1：sum=4，剩余 i=4, m'=max(1,1)=1，dp[4][1]=4，所以收益 = 4 - 4 = 0。
     • x=2：sum=8，剩余 i=5, m'=max(1,2)=2，dp[5][2]=0，收益 = 8 - 0 = 8。
       取最大值，dp[3][1] = 8。
   • m=2：可取 1~4 堆，但只剩 2 堆，x=1 收益=4-4=0，x=2 收益=8-0=8，所以 dp[3][2]=8。
5. 计算 i=2（堆[9,4,4]）：
   • m=1：可取 1~2 堆。
     • x=1：sum=9，剩余 i=3, m'=1，dp[3][1]=8，收益=9-8=1。
     • x=2：sum=13，剩余 i=4, m'=2，dp[4][2]=4，收益=13-4=9。
       取最大值 9，dp[2][1]=9。
   • m=2：可取 1~4 堆，剩 3 堆。
     • x=1：收益=9-8=1。
     • x=2：收益=13-4=9。
     • x=3：sum=17，剩余 i=5, m'=3，收益=17-0=17。
       取最大值 17，dp[2][2]=17。
6. 类似计算 i=1、i=0，最终 dp[0][1] = 9（>0），所以先手能赢。

关键点

• 状态定义是“领先分数”，简化了两人得分分别记录的复杂。
• 取石子只能从左侧连续取，所以状态只用一个起始下标 i，而不是区间 [i,j]。
• M 会增长，需在状态中记录 m。

复杂度
状态数 O(n²)，每个状态需枚举 x 最多 2m 次，m 最大 n，总复杂度 O(n³)，但可优化：当 m 较大时，2m 可能超过剩余堆数，实际枚举 x 最多 n 次。对于 n ≤ 100 可接受。

思考扩展
若规则改为从数组两端取石子（类似石子游戏 I），则需用区间DP，状态为 dp[i][j][m] 表示剩余石子为 piles[i..j] 时的领先分数。本题因只能从左侧取，简化为一维起始点。