不久前我發(fā)布了一個問題征答：在這個砍九頭蛇的游戲中，以最快的方法去砍，最終砍掉四層節(jié)點的九頭蛇需要多少步？即optimal_hydra(4)等于幾？很快我收到了3份解答，所有解答者都給出了optimal_hydra(4)的確切數(shù)字，它是一個有13598位的巨大數(shù)字：

??

這三位給出解答的讀者分別是（按來信先后）：Salviatia, Kano，思銘寶寶。Salviatia說已經(jīng)有我的書了，所以恭喜Kano得獎了。也同時贊一下三位的解答和思考能力。以下我借用一下“思銘寶寶”的解題思路，因其思路最簡潔。另外Kano還給出了其對這個砍九頭蛇游戲最佳和最差步數(shù)的分析，稍后我會轉(zhuǎn)載出來?！八笺憣殞殹苯o我的電郵里是這樣寫的（略修改）：

我運用了大老李給出的貪心算法，先去最深的括號，深度相同時先去兄弟多的括號。
首先定義一個函數(shù)step(k,n,m)
表示已經(jīng)進行了k步。形成如下的括號串：



如此進行(到)step(k,n,m)步（包括開始的k步），使得括號串變?yōu)椤?)”。(大老李注：本解釋中的“步數(shù)”都是計數(shù)的含義，即“運行到某某步”，而不是“再運行xx步”的意思)

那么面對這樣的括號串應(yīng)當(dāng)如何去括號呢？首先進行m步，這樣使m個子括號串變?yōu)?br>

那么一共增加了多少子串呢？則為：

算上原先的m個，則為：


于是就有了轉(zhuǎn)移方程：


但當(dāng)n=0時，其總步數(shù)就為k+m，Python代碼如下（ https://code.sololearn.com/cA10A1A18A7a , 直接看運行結(jié)果）：

下面我模擬一下五重括號的過程：

到第五步，其內(nèi)層一共有15個括號，對應(yīng)：

k=5 n=15 m=1

所以答案呼之欲出：

optimal_hydra(4)=step(5,15,1)

....

當(dāng)然，我感覺也可用類似的方法寫出optimal_hydra(n)的遞推公式。

所以，根據(jù)以上，只要5行代碼，就可以算出optimal_hydra(4)的確切值，且一瞬間就可以執(zhí)行完成！但是問題沒完，我們很想寫出能計算一般的optimal_hydra(n)的程序。

借用“思銘寶寶”的思路，大老李做了如下分析，考慮在“去括號游戲”中的這種形態(tài)：所有最內(nèi)層括號都在同一層且互為“兄弟”，外圍有i重括號，兄弟一共m個，此時進行到第s步：

第s步:

下一步會變?yōu)椋?br>
第s+1步:?

又經(jīng)過若干步，遲早會變?yōu)椋?br>
第s+x步:??

其中的x, y是可以由初始的i, m, s唯一確定計算出的。分析出x, y與i, m, s的關(guān)系后，就可以寫出一般的計算optimal_hydra(n)的[程序](https://code.sololearn.com/ca23a121a19A)：

當(dāng)然，由于函數(shù)值增長的過快，程序無法計算出optimal_hydra(5)的結(jié)果。如果用Oh(5)和Oh(4)分別表示optimal_hydra(5)和optimal_hydra(4), 大老李初步分析:

也歡迎你發(fā)給我你對hydra(n)的大小估計。這是一次非常有意義的編程經(jīng)歷，大老李寫出了一個平生最“喪心病狂”的，但可以計算出確切值的和有意義的大數(shù)函數(shù)！