LC 1872. 石子游戏 VIII

https://leetcode-cn.com/problems/stone-game-viii/

还是动态规划，还是要讲究计算顺序，才能得到子问题的最优解。

这题如果上来就想"在ith取石子的话，alice-bob的值最大可以是多少”，这种动态规划方法就是O(n^2), 显然是会超时的。这似乎是从后向前的思路。

从前向后的思路是，dp[i] 表示 "当前人A（可以是alice/bob）在这个位置开始取石子， A-B的最大差值是多少"

如果A取了ith的石子的话，那么获得了 prefix[i] 的分数，剩下就是 -dp[i+1] 的分数了。
如果A没有在ith取石子的话，那么就是 dp[i+1]
所以 dp[i] = max(prefix[i] - dp[i+1], dp[i+1])
最终值是 dp[1]. 因为alice开始必须要取1个石子

这个推导公式继续往下的话，可以去掉数组只留下2个变量

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        acc = [0] * (n + 1)
        for i in range(n):
            acc[i + 1] = stones[i] + acc[i]

        # 状态方程是dp[i]表示从i开始选择，alice-bob的最大差值
        # alice不选择ith的话，那么dp[i] = dp[i+1]
        # 如果选择ith的话，那么alice获得acc[i+1] value,
        # 接下来就是bob取，所以dp[i] = acc[i+1] - dp[i+1]

        dp = [0] * n
        dp[n - 1] = acc[n]
        # dp[i] = max(dp[i+1], acc[i+1] - dp[i+1])
        for i in reversed(range(1, n-1)):
            dp[i] = max(dp[i+1], acc[i+1] - dp[i+1])
        # have to take one stone.
        ans = dp[1]
        return ans