净胜分心法：让你还没摸牌就知道会不会赢

一、牌桌之上，零和博弈

澳门，皇家赌场，半夜十一点。

你坐在牌桌左边，手里转着一块还没拆锡纸的巧克力。

对面是欧洲赌魔 查尔斯，金发梳得油光水滑，身后站着四个保镖，人手一本《博弈论》。

“今晚我们不玩梭哈。” 查尔斯笑容倨傲。

他打了个响指。荷官推出一个牌匣，里面躺着一排牌，牌面上不是花色，而是数字：

[1, 5, 233, 8, 2, 6, 4, 3]

八张牌，张张点数透明。像一局明棋，沉默地躺在绿色绒布上。

“规则很简单——我们轮流从这排牌的最左端或最右端抽一张。抽到的数字直接加进总分。牌抽完，分高的人赢。如果平局——”他顿了一下，镜片反光一闪，“算你先手赢。”

你慢慢拆开巧克力的锡纸。

“我研究过你所有的录像。”查尔斯推了推眼镜，“你擅长在最后一刻翻盘，用一张小牌撬动整个局面。但这一次——每张牌的点数都直接公开，双方都绝对理性，追求自己的最大利益——你没有出千的空间。”

你咬了一口巧克力：“你研究过我——那你知道为什么赌神从来不输吗？”

查尔斯冷笑：“因为你出老千？”

“不。”你把锡纸叠成一只纸鹤，放在牌匣旁边，“因为我会在游戏开始前，就把结局算死。”

二、净胜分——赌神只看一件事

阿星从旁边探出头，手里还举着半瓶汽水：“哥，要不要我用特异功能帮你搓一下牌？八张牌，我把那个 233 搓到最右边，你开场就给它抽走。”

你按住他的手，“搓牌？搓完你晚上又流鼻血。今天教你一套正经功夫——递归动态规划无死角净胜分心法。”

阿星一口汽水差点喷出来：“名字这么长？！能不能取个酷一点的简称？”

“江湖上都叫它——先手判生死。”

你在桌布上用手指画了两个字母，diff(l, r)，“阿星，两个高手博弈，你知道最难算的是什么？”

“当然是算总分啊！你一张我一张，你永远猜不到对方下一步要拿哪张，算到最后脑子都炸了。”

“错。总分是下等赌客算的。真正的高手，只算一个数——我比你多赢多少。”

阿星眨了眨眼：“多赢多少？”

“净胜分。”

设 diff(l, r) 表示： 当桌上只剩下第 l 张到第 r 张牌，且现在轮到某人抽牌时，这个“当前抽牌人”最多能净胜对手多少分。

净胜分 = 我的总分 – 对手的总分。

“查尔斯和我轮流抽，规则简单到三岁细路仔都识：

• 如果我从左端抽第 l 张，我立刻到手 nums[l] 分。

• 抽完之后，桌上剩下 [l+1, r]。轮到对手抽。注意——对手也是绝顶聪明的人渣，他也会最大化他自己的净胜分，也就是他能拿到 diff(l+1, r) 的净胜分。

• 那我的最终净胜分是多少？我手里的 nums[l]，减去对手的净胜分。也就是：

  左端净胜 = nums[l] - diff(l+1, r)
  

• 同样，如果从右端抽：

  右端净胜 = nums[r] - diff(l, r-1)
  

• 两条路摆在面前，当然选净胜分更大的那条：

  diff(l, r) = max( nums[l] - diff(l+1, r),
                    nums[r] - diff(l, r-1) )
  

阿星听到这里，抓了抓头发：“等一下哥。你左边写了个 diff(l, r)，右边又蹦出来 diff(l+1, r)——这公式自己调用自己，这不就是那个、那个——递归吗？我听说递归这东西，搞不好会 stack overflow 的！”

“递归当然要有边界，不然就是死循环——你打麻将只摸牌不出牌，牌局能结束吗？” 你把纸鹤转了个方向，翅膀对准他，“只剩一张牌（l == r）的时候，就是边界。只有一张牌还选什么？直接抽走。当前抽牌人的净胜分就是 nums[l] 本身。”

“所以，只需要算出 diff(0, n-1)——也就是整副牌、我先手时的最大净胜分。如果这个数大于等于 0，我就至少不输。按照规则，平局也算我赢。这局，在抽第一张牌之前就已经结束了。”

三、第一张牌

八张牌安静地躺在绿绒布上，最大的一张 233 缩在左手第三张，像一块被瓦片盖住的金砖。

你把巧克力塞进嘴里，闭上眼睛。手指悬在桌面上方，像在敲击一张看不见的键盘——实际上你脑子里那张 DP 表正在从对角线往外一层层填满。八张牌，六十四格。净胜分在翻来覆去地拉扯，最后定格在一个数字上。

你睁开眼睛，“阿星，我的全局净胜分大于 0。这一局，我已经赢了。”

阿星瞪大眼睛：“哥，你连牌都没摸呢，这么肯定？！”

你没搭话，伸出手，在所有人的注视下，抽走了最左边那张牌——1。

查尔斯愣了一秒，然后大笑，“这就是赌神？闭眼算了半天，第一步居然拿了个最小的 1？”

桌上剩下七张：[5, 233, 8, 2, 6, 4, 3]。轮到查尔斯。

他活动了一下手指，伸向最左的 5，停住了。又伸向 3，又停住了。

他的脸色骤变，冷汗从他太阳穴滑下来。

“如果我拿 5——剩下 [233, 8, 2, 6, 4, 3] 给你。你第一张就会直接叼走 233，然后桌上变成 [8, 2, 6, 4, 3] 轮到我。不管我接下来怎么选，只能捡些8、4、6 这种零钱，根本追不上！”

“如果我拿 3，剩下 [5, 233, 8, 2, 6, 4] 给你——你肯定不会拿 5，因为拿 5 等于把 233 留给我。你一定会拿 4！然后剩下 [5, 233, 8, 2, 6] 轮到我。我被迫拿 6，然后你拿 2，我拿 8，233还是你的！我怎么选都死？！”

查尔斯的金丝眼镜裂开一条缝。他终于明白了——那张 1 是一把钥匙。拿走了 1，你变成了游戏规则的掌控者。他不管从左走还是从右走，都会亲手把通往 233 的路给你让出来。

你咬了一口巧克力：“这就叫，用对手的手，帮自己拿牌。”

尾声：

查尔斯瘫在椅子上，四个保镖手忙脚乱地翻《博弈论》索引，嘴里念念有词：“Minimax……Nash equilibrium……不对不对老板，这章我们还没读到——”

“读个屁。”查尔斯有气无力地挥了挥手，“明天给我换一本《算法导论》。”

你起身整理西装，把那只纸鹤留在牌匣旁边，翅膀正对着查尔斯。

“用算法的话说，这叫——最优子结构。把大问题拆成小问题，每一步都在替对手关上他最想走的那扇门。”你转身走向门口，头也不回，“先手判生死——承让。”

阿星看着你背影大喊：“大哥！这招式能不能写短一点？我要纹在手臂上！”

你头也不回，弹出一张扑克牌，上面用缩进刻着：

def predictTheWinner(nums):
    @cache
    def dfs(start: int, end: int) -> int:
        if start == end:
            return nums[start]
        return max(nums[start] - dfs(start + 1, end), nums[end] - dfs(start, end - 1))

    return dfs(0, len(nums) - 1) >= 0

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。