[G 家 onsite 题] 探讨 Stone Game (LC877) 的扩展：3 个 player 的 Stone Game

Stone Game 大家应该很熟悉了，这里简单说一下：

有 N 堆石头排列成一排，用数组 piles[0, ..., N-1] 表示，piles 代表第 i 堆石头的个数。两个玩家轮流从 piles[] 里拿石头，每次可以拿 1、2 或 3 堆（不能不拿，且如果拿了某堆，就要把该堆石头全部拿走）。最终当 piles 被拿完时，石头总数多的一方获胜。

两个玩家时，是零和游戏，所以可以用 DP + Minmax 的方式解决。但是当三个玩家时候（其它规则不变，游戏顺序：玩家 1、玩家 2、玩家 3），应该怎么解这道题呢？

G 家 virtual onsite 时候遇到了这个题（三人），lz 没解出来。

补充内容 (2020-11-26 00:47):
补充一下：忽略一个细节，和 LC 原题不一样的是，只能从头拿：

拿 piles[0]
拿 piles[0], piles[1]
拿 piles[0], piles[1], piles[2]

愤怒的小蚯蚓 发表于 2020-11-25 11:24
我去....三个人？

补充内容 (2020-11-25 11:25):

我也是这么觉得，因为不再是零和了。

愤怒的小蚯蚓 发表于 2020-11-25 11:55
还是零和，只是 是 多方的零和博弈...

补充内容 (2020-11-25 11:56):

这么说也对，但是多方的话确实不知道应该如何下手。

三个player每人max自己的score应该就可以了吧，三维dp或者recursion with memorization

a(i,j) -> (score_a, score_b, score_c) : max score a can achieve if a starts picking a pile in the current settings
b(i,j) -> (score_a, score_b, score_c) : max score b can achieve if b starts picking a pile in the current settings
c(i,j) -> (score_a, score_b, score_c) : max score c can achieve if c starts picking a pile in the current settings

a(i,j)计算方法：
if i ==j:
    a(i,j) = (piles,0,0)
else:
    ah,bh,ch = b(i+1,j)
    at,bt,ct = b(i,j-1)
    if ah+piles >  at+piles[j] or ah+piles ==  at+piles[j] and max(bh,ch)<=max(bt,ct):
        a(i,j) = (ah+piles, bh,ch)
   else:
        a(i,j) = (at+piles[j], bt,ct)
把a(i,j)存一下加速计算。
要考虑break tie的情况因为现在有3个人，取头尾都一样的话应该取让除了当前player之外的最高的那个人少拿的case

补充内容 (2020-11-26 02:07):
a(i,j)意思是现在轮到a来拿，piles现在可以拿的pile是从i到j的这些piles

只能从头尾拿？