1872. 石子游戏 VIII 详细介绍推导过程

1872. 石子游戏 VIII

​ 这道题官网有很多很好的解释，这里结合我自己的思考介绍是怎么一步步从最原始的解法再到优化出 $O(n)$的解法的过程。也可以理解为是对转移方程

$f[i]=max(f[i+1],pre[i]−f[i+1])$ 的一个补充说明

比较关键的一步是要发现出“前缀和”这个重点。

通常来说，石子游戏系列都可以通过自己“画”出一棵树来看是怎么从上而下得到结果的。但是如果这里我们直接从最原始的输入来画的话，就会得到下面这种图。输入：$stones = [-1,2,-3,4,-5]$。

上图是遍历出每一轮的选择的结果。其中，正方形代表的是轮到Alice选，圆形代表的是轮到Bob选。但是，注意到Alice和Bob都想作出对自己最优的选择。假设最终的结果的选择是$A_1 + A_2 + … + A_x – (B_1 + B_2 + … B_y)$。 那么当Alice面对输入$[-1,2,-3,4,-5]$的时候，从上图可知，他一共有4个选择，而且他最终肯定是选择：