> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0877_stone_game/slt.md).

# Solution1 DP

* 时间复杂度 O(n^2)
* 空间复杂度 O(n^2)

`dp[l][r]` 表示在区间\[l, r] 内，双方都做最优选择的情况下，先手与后手的得分差值

则 dp\[1]\[n] 是 n 个堆的所有石子的双方的差值

* dp\[1]\[n] > 0，则先手赢
* dp\[1]\[n] < 0，则后手赢

不可能相等，应为总石子是奇数

状态转移方程：

这次先手从左边取（减去\[l+1, r]中的最佳决策）

最大差值a = piles\[l-1] - dp\[l+1]\[r]

这次先手从右边取（减去\[l, r-1]中的最佳决策）

最大差值b = piles\[r-1] - dp\[l]\[r-1]

dp\[l]\[r] = max(a, b)