赌城风云·续：阿星的出师之战

又名：《阿星的单飞考试：递归会流鼻血，滚动数组才是王道》 前情提要：上一局，你用"净胜分心法"碾压了欧洲赌魔查尔斯（）。他回去苦读《算法导论》，三个月后卷土重来。

一、查尔斯的复仇

三个月后。同一张牌桌，同一盏水晶吊灯。

查尔斯又来了。

这一回他的金发梳得更亮，领带换成了深红色——据说是专门找人算过的“必胜色”。身后还是那四个保镖，但手里的书已经从《博弈论》换成了崭新的《算法导论》，书签统一夹在动态规划那一章。封面还贴着便利贴，上面写着：“注意最优子结构！！！”

“三个月，”查尔斯站在牌桌对面，金丝眼镜换了一副，镜片更厚，反光更刺眼，“我在剑桥旁听了一整个学期的算法课——你的净胜分心法，我已经吃透了。”

你坐在牌桌左边，手里转着一块新的还没拆锡纸的巧克力。听完这句话，你停下手里的转动，然后做了一个让全场倒吸一口凉气的动作——站起来，退后三步，把椅子让给了身后的阿星。

“今天不是我跟你打。”你拍了拍阿星的肩膀，“你跟我徒弟打。”

阿星正举着半瓶汽水，差点呛到：“我？！哥，我就是个跑龙套的！我连《算法导论》封面长什么样都不知道！”

“你跟了我这么久，该出师了。”你把巧克力外面的锡纸剥开，掰下半块递给阿星。

查尔斯先是愣了一下，然后笑出声：“让你徒弟来送分？好，正好——新规矩，新牌局。”

他打了个响指。荷官推出一副新牌匣，牌面朝上，一字排开：[1, 3, 2, 50, 9, 90, 30, 90, 2, 8, 4]。

“规则升级了。”查尔斯推了推新眼镜，“还是轮流抽，但这一回——只能从最前面开始拿。每次可以拿走 1 张、2 张、或 3 张牌。拿走的牌面数字直接加进你的总分。所有牌拿完，分高的人赢。平局算 Tie。”

他往椅背上一靠，嘴角挂着一丝“我连你徒弟的墓碑都想好写什么了”的微笑。

“对了——为了公平起见，今天的先手，我们抽签决定。”他掏出一枚硬币，在指缝间转了一圈，“我也不欺负晚辈。抽签定先手，各自凭运气。”

阿星还没来得及抗议，你已经在旁边的沙发上坐下了。包装巧克力的那张锡纸已经被你折成了一只纸鹤，立在茶几上，翅膀微微翘起，正对着牌桌。“阿星，我教你的东西，这三个月你琢磨了几回？”

“呃……三回？”

“够了。打吧。”

二、阿星的独角戏

阿星坐到牌桌左边，手心全是汗。他把牌从左到右看了三遍，嘴里开始念念有词。

他在做一件每个初学者都会做的事——暴力递归。

“好，先定义一个函数 dfs(i)，表示从第 i 张牌开始先手，最多能比对手多拿多少分。”阿星掰着手指，声音越来越大，像是在给自己壮胆，“从第 i 张开始，我可以拿最前面的 1 张、2 张、或 3 张。拿走的牌面总分记作 take，留给对方的是 dfs(i+1)、dfs(i+2)、dfs(i+3) 三种局面——”

他在桌布上画了一个递归树，从 dfs(0) 开始分叉，“dfs(0) 等于 max(拿1张 - 对手dfs(1)的净胜, 拿2张 - 对手dfs(2)的净胜, 拿3张 - 对手dfs(3)的净胜)……”。一叉分三叉，三叉分九叉——画到第三层的时候，桌布已经不够用了。他把袖口也翻出来接着画，画到第四层，指尖开始发抖，额头上冒出一层细汗。

n = len(stoneValue)

@cache
def dfs(i):
    if i == n:
        return 0
    best = float('-inf')
    take = 0
    for j in range(i, min(i + 3, n)):
        take += stoneValue[j]
        best = max(best, take - dfs(j + 1))
	return best

diff = dfs(0)
return "Tie" if diff == 0 else "Xin" if diff > 0 else "Charles"

阿星感觉递归树在他脑子里疯狂生长，每多一层就多三倍的分支，像一棵没人修剪的野树，枝杈戳得到处都是。

突然——一滴红色的液体落在了桌布上，恰好滴在 dfs(2) 的圆圈里。

阿星流鼻血了。

“哥！”他捂着鼻子转头看你，“递归太深了，我脑子要爆栈了！”

查尔斯差点笑得从椅子上滑下去：“这就是赌神的徒弟？算了三分钟就开始流鼻血？”

你放下茶杯，不紧不慢地走到阿星身边，从口袋里掏出一张纸巾，“谁让你用脑袋递归了？”

你把纸巾按在他鼻子上，“三个月前教你的 DP 表呢？再说一遍——人类的大脑不适合递归，但可以填表。”

三、从全表到滚动数组

“递归是从头往下分叉，分到最后自己都不知道自己在哪一层。”你又从桌上抽了张干净纸巾，盖住桌布上那团被鼻血渗透的 dfs(2)，“填表不一样——从尾巴往前推。你想想，如果只剩下最后一张牌，你拿还是不拿？”

“当然拿啊，”阿星捂着鼻子，瓮声瓮气地说，“不拿白不拿。”

“对。最后一张的净胜就是它自己。那如果剩下最后两张呢？你有三个选择——拿一张，留一张给对手；拿两张，清盘。每个选择的净胜分用‘take - 对手在剩余牌面的净胜’来算，选最大的那个。就这样，从后往前，每一步都站在前一步已经算好的答案上，一层一层盖楼。”

阿星想了想：“那就开一个 dp 数组，从 dp[n-1] 一路算到 dp[0]？

n = len(stoneValue)

dp = [-float('inf')] * n + [0]  # 末尾多一个 0 当哨兵，越界返回 0
for i in range(n-1, -1, -1):
	take = 0
	for j in range(i, min(i + 3, n)):
		take += stoneValue[j]
		dp[i] = max(dp[i], take - dp[j + 1])

return "Tie" if dp[0] == 0 else "Xin" if dp[0] > 0 else "Charles"

“对——”，你点点头：“但还可以再省。”

你用指尖划过阿星手边的汽水瓶——瓶壁上凝着一圈细密的水珠——就着那点凉意在纸巾上画下三个字符：i1, i2, i3。“你注意到没有——算 dp[i] 的时候，你只需要它后面的三个值(dp[i] 只依赖 dp[i+1]、dp[i+2]、dp[i+3])。之前的值用完就可以扔了。所以——三个变量就够了，从后往前滚，空间压成 O(1)。”

阿星瞪大眼睛：“三个变量？”

“滚动数组——你只需要记住最近三个净胜分。”

n = len(stoneValue)

i1 = i2 = i3 = 0  # 分别存 dp[i+1], dp[i+2], dp[i+3]
for i in range(n - 1, -1, -1):
    take = 0
    best = float('-inf')
    for j in range(i, min(i + 3, n)):
        take += stoneValue[j]
        if j == i:
            opponent = i1
        elif j == i + 1:
            opponent = i2
        else:
            opponent = i3
		best = max(best, take - opponent)
		i1, i2, i3 = best, i1, i2
        
return "Tie" if i1 == 0 else "Xin" if i1 > 0 else "Charles"

阿星攥紧了纸巾，盯着那三个变量在心里跑流程。他的嘴唇翕动着，从最后一堆开始往前滚——i3 是越界的 0，i2 是最后一张的净胜，i1 是倒数第二张的净胜——三个数字像三个齿轮，一步一步从尾巴咬到头。

滚到 i=0 的时候，他停住了。

“i1 等于……”他抬头看你，声音压到只有你能听见：“——负的，全局先手必输。”

他抬头看你，声音压到只有你能听见：“哥，净胜分是负数，全局先手必输。Alice 在这个数组上拿先手，净胜是负的。”

你端起茶杯，吹了吹浮在面上的茶叶，没说话。

阿星看着你那个表情，忽然想起了三个月前你说的话——“在游戏开始前，就把结局算死”——他明白了：算牌只是第一步，把算出来的结局钉死在牌桌上，才是真正的考验。

四、欲盖弥彰

阿星深吸了一口气，把纸巾揉成一团塞进裤兜，然后仰头看了会儿天花板，让鼻血彻底凝固。他需要这几秒钟——不是因为鼻子，是因为他得把“先手必输”四个大字从脸上抹干净，换上一张无辜的、甚至有点得意的脸。

然后——他开始笑。

笑得不大，但刚好能让对面听到。嘴角一抽一抽的，像是发现了什么不得了的秘密，又拼命想藏住。

查尔斯正用眼镜布擦镜片，手停了。他盯了阿星两秒，那两秒里阿星做了全套——先飞快地把笑容收回去，收得太快，像被抓包；然后把目光移开，假装研究天花板上的吊灯，眼珠子转得过于刻意；最后用袖子漫不经心地往桌布上一盖，恰好盖住那片被汽水字迹和鼻血交替浸过的纸巾碎片。

“你笑什么？”查尔斯把眼镜戴回去。

“没什么没什么，鼻子通了，高兴。”阿星站起来，身体不自觉地挡在桌布前面。一只手在背后悄悄把裤兜里那团揉皱的纸巾往里塞了塞，动作大得生怕对面四个保镖有一个没看到。

果然，一个保镖低头在查尔斯耳边说了句什么。查尔斯的眉头慢慢皱了起来。他用手指敲着桌面，“你的表情，就像算出了不得了的东西——你在算先手还是后手赢，对不对？”

阿星的表情僵了一瞬——这一瞬的僵硬，足够让查尔斯确认自己猜对了。

“阿星，”查尔斯往前倾了倾身子，金丝眼镜后的目光像两颗瞄准激光，“你刚才是不是算出来，先手必赢？”

阿星的瞳孔微微放大。这个表情就像被人当众翻开底牌——不，像是被人猜中了自己正在拼命隐藏的结论。他飞快地摇头：“不是不是，我什么都没算出来……递归太深，我流鼻血了，脑子不清醒……先手后手什么的，我觉得应该差不多吧，五五开，运气最重要。”

“五五开？你刚才算到流鼻血，然后就开始笑，现在又跟我说五五开？”查尔斯眯起了眼睛，“你在说谎。”

阿星的额头上沁出了一层细密的汗。骗一个在剑桥旁听过一学期算法的聪明人，每一步都不能踏错。假话要混在真话里说，表情要半真半假，最难的是眼神——你不能直视他，但也不能完全躲开。你得让他觉得你在躲，但又让他恰好能捕捉到你“不小心”漏出来的破绽。

“查尔斯先生，”阿星突然站直了，语气变得异常认真，仿佛刚才的慌张全是铺垫，现在才是真情流露，“今天我师父不在桌上，我就是来练手的。你先手的话太欺负人了——你算法课上了三个月，我才琢磨了三回。这局让我先手，公平点。”

他说“公平点”三个字的时候，眼神里甚至带着一丝恳求，嘴角用力抿着，像在做最后的挣扎——明明知道对方不可能答应，还是硬着头皮把话说出来，试图用道德绑架一个没有道德的欧洲赌魔。

查尔斯看着阿星那张真诚的脸，慢慢笑了。先是嘴角，然后是眼角，最后整个肩膀都在抖。他等这一刻等了三个月。三个月前他被先手的一张 1 玩死，回去以后在笔记本上写了三百遍——“先手才是庄家。后手只能被动反应。”

“我先手。”查尔斯一锤定音。

“等一下！让我先手！”阿星的肩膀轻微地抖了一下，像是最后一根弦被扯断了，他张着嘴，手还僵在半空中，语气低落得像是被抽走了半条命，“……你连硬币都不抛了？”

“硬币？”查尔斯把硬币收回胸口的西装口袋，拍了两下，金丝眼镜后的眼睛弯成了两道得意的弧线，“不需要了。你的表情，你的小动作，你拼命想藏起来的那团纸巾——每个信号都指向同一件事：你算出来了先手必赢，你想抢那个先手。既然你想抢——我为什么要让给你？”

五、注定的结局

接下来的每一轮里，阿星只是安静地拿牌。每一轮都拿得不快不慢，没有得意，也没有犹豫。他不需要再算了——整局的结果在查尔斯拿先手的那一刻就已经钉死了。

牌局很快结束。荷官按下计算器，报出两个总分。

“怎么可能——” 查尔斯的脸色从红变白，从白变青。他低头看着桌上的牌，又抬头看着阿星，嘴张了两次都没再发出声音。然后他猛地站起来，椅子在身后发出刺耳的摩擦声。

“你不是流鼻血了吗——不对，你从一开始——”查尔斯的手指在阿星和牌桌之间来回弹跳，像一台卡壳的打字机，“你从一开始就知道了！全局先手必输！但你故意让我以为先手必赢。你刚才那个表情——那个藏桌布、藏纸巾、求我让你先手的表情——全是演的！！”

阿星缓缓站起来，从裤兜里掏出那张揉皱的纸巾，展开铺平在牌桌上。上面还留着汽水干透后浅浅的水渍。

“我师父三个月前教我的——在游戏开始前，就把结局算死。”阿星把纸巾推到牌桌中央，“净胜分心法第二条——你抢过去的先手，可能恰好是我算好了要送给你的。”

六、赌神的进阶

查尔斯被四个保镖架走了。临走时嘴里还在念叨“净胜分”和“先手后手”，金丝眼镜断成两截挂在耳朵上，像一对垂头丧气的翅膀。

阿星一直目送查尔斯的背影消失在旋转门后面，才长长地吐了一口气。他把牌桌上的汽水端起来咕咚咕咚灌了半瓶，然后转头看向你，“哥，刚才那段演技，我自己都有点没底——藏纸巾那一下是不是演得太用力了？”

“演技确实是浮夸了点——但逻辑没问题，你赢了。”你从沙发上站起来，走到牌桌旁边，“但是——净胜分的视角，还不够简洁。”

阿星一愣。

“净胜分确实没错。能赢。但还不够简洁。”你在纸上画了一个新的结构，“你刚才一直算的是‘我比你多赢多少’，但你有没有想过——直接算‘我能拿多少分’？”

阿星一愣：“不够简洁？不是都已经把空间压到三个变量了吗？”

“不是在空间上。是在思路上。”你在牌桌对面坐下，“你每次轮到你拿牌的时候，是不是要在心里跑一遍内层循环？拿一堆算一遍 take - opponent，拿两堆算一遍，拿三堆再算一遍，三个分支比完才敢下手。”

阿星想了想，点头：“确实。每次到我，我都得在脑子里过三个选项。虽然能算出来，但总觉得中间多了一层——像脑子里有个翻译官，把我想拿的分数先翻译成‘比对手多多少’，比完了再翻译回来。”

“因为净胜分的视角，天然多了一层。你有没有想过——不记录净胜分，直接算当前牌面‘你能拿到的最大总分’？”

阿星一愣，然后微微坐直了身体。

“换个视角。”你抽出一张纸，写下新的定义，“定义 f[i]：从第 i 张牌开始先手的玩家，在剩余牌面中能拿到的最大总分。注意——这次不是差值，就是你自己的总分。不关心对手拿多少，只关心你自己能装进口袋多少。”

“从后往前看。只剩最后一张牌的时候，你拿走它，你的总分就是它本身。那如果从中间某张牌开始呢？每一轮你可以拿最前面的 1 张、2 张或者 3 张。不管你拿几张，从当前这张到末尾的总和——后缀和——是一个死的数。你拿走一部分，剩下的全归对手。对手在他拿到的那部分里，也会用最优策略拿走他的最大总分——那就是 f[i+j]。”

你停下来，让他消化这个概念。“所以每轮牌面，你能拿到的最大总分等于什么？后缀和 - 对手在剩下牌局里能拿到的最大总分。”

s[i] = 从 i 到末尾的后缀和 f[i] = s[i] - （对手在剩余牌面里能拿到的最大总分）

“重点来了——要最大化你能拿到的，就要最小化对手能拿的——对手在剩余牌面里能拿多少？取决于你。你拿 1 张，剩给他的是从 i+1 开始——他最多能拿 f[i+1]。你拿 2 张，剩给他的是从 i+2 开始——他最多能拿 f[i+2]。你拿 3 张，他最多能拿 f[i+3]。最小化对手能拿的，也就是在这三个数中选最小的那个——min。”

f[i] = s[i] - min( f[i+1], f[i+2], f[i+3] )

阿星盯着那个 min，张了张嘴。这个反应和你预计的一模一样。

“而且——后缀和只依赖当前位置，后面三个 f 也只依赖紧挨着的三个状态。和刚才净胜分的滚动数组一模一样的依赖关系：f[i] 只跟 f[i+1]、f[i+2]、f[i+3] 打交道，再往后的值碰都不碰。同样不用数组，直接可以用三个变量滚完全局。”

n = len(stoneValue)

s = f1 = f2 = f3 = 0
for i in range(n-1, -1, -1):
	s += stoneValue[i]
    best = s - min(f1, f2, f3)
	f1, f2, f3 = best, f1, f2
    
diff = f1 - (s - f1)
return "Tie" if diff==0 else "Xin" if diff>0 else "Charles"        

“这就是思维翻转——视角一换，内层循环直接消失。”你从口袋里掏出一块新的巧克力，掰了一半递给阿星。

“净胜分算的是两个人的博弈——你要在三个分支里分别算‘我比他多多少’，所以需要内层循环去模拟拿一张、两张、三张的分支。而总分算的是一个人的收益——你不需要关心对手具体拿多少，你只需要让他在剩给他的局面里，拿得越少越好。后缀和是死的，min 三个 f 锁定对手的下限，你拿的自然就最大。”

阿星把那半块巧克力塞进嘴里，低头看了看自己两条小臂——左胳膊上还隐约能看见三个月前用圆珠笔写的“先手判生死”，已经褪得只剩浅浅一道印子；右胳膊干干净净，像是特意留到今天。

“哥。左胳膊纹净胜分，右胳膊我想纹这个 min。”

你把另外半块巧克力放进嘴中，起身拿起茶几上的纸鹤，放在他手心。

“先回去把鼻血擦干净。纹身师不接流着血来的人。”

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