最快砍“九头蛇数”问题的解答

不久前我发布了一个问题征答：在这个砍九头蛇的游戏中，以最快的方法去砍，最终砍掉四层节点的九头蛇需要多少步？即optimal_hydra(4)等于几？很快我收到了3份解答，所有解答者都给出了optimal_hydra(4)的确切数字，它是一个有13598位的巨大数字：

  

这三位给出解答的读者分别是（按来信先后）：Salviatia, Kano，思铭宝宝。Salviatia说已经有我的书了，所以恭喜Kano得奖了。也同时赞一下三位的解答和思考能力。以下我借用一下“思铭宝宝”的解题思路，因其思路最简洁。另外Kano还给出了其对这个砍九头蛇游戏最佳和最差步数的分析，稍后我会转载出来。“思铭宝宝”给我的电邮里是这样写的（略修改）：

我运用了大老李给出的贪心算法，先去最深的括号，深度相同时先去兄弟多的括号。
首先定义一个函数step(k,n,m)
表示已经进行了k步。形成如下的括号串：



如此进行(到)step(k,n,m)步（包括开始的k步），使得括号串变为“()”。(大老李注：本解释中的“步数”都是计数的含义，即“运行到某某步”，而不是“再运行xx步”的意思)

那么面对这样的括号串应当如何去括号呢？首先进行m步，这样使m个子括号串变为

那么一共增加了多少子串呢？则为：

算上原先的m个，则为：


于是就有了转移方程：


但当n=0时，其总步数就为k+m，Python代码如下（ https://code.sololearn.com/cA10A1A18A7a , 直接看运行结果）：

下面我模拟一下五重括号的过程：

到第五步，其内层一共有15个括号，对应：

k=5 n=15 m=1

所以答案呼之欲出：

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

....

当然，我感觉也可用类似的方法写出optimal_hydra(n)的递推公式。

所以，根据以上，只要5行代码，就可以算出optimal_hydra(4)的确切值，且一瞬间就可以执行完成！但是问题没完，我们很想写出能计算一般的optimal_hydra(n)的程序。

借用“思铭宝宝”的思路，大老李做了如下分析，考虑在“去括号游戏”中的这种形态：所有最内层括号都在同一层且互为“兄弟”，外围有i重括号，兄弟一共m个，此时进行到第s步：

第s步:

下一步会变为：

第s+1步: 

又经过若干步，迟早会变为：

第s+x步:  

其中的x, y是可以由初始的i, m, s唯一确定计算出的。分析出x, y与i, m, s的关系后，就可以写出一般的计算optimal_hydra(n)的[程序](https://code.sololearn.com/ca23a121a19A)：

当然，由于函数值增长的过快，程序无法计算出optimal_hydra(5)的结果。如果用Oh(5)和Oh(4)分别表示optimal_hydra(5)和optimal_hydra(4), 大老李初步分析:

也欢迎你发给我你对hydra(n)的大小估计。这是一次非常有意义的编程经历，大老李写出了一个平生最“丧心病狂”的，但可以计算出确切值的和有意义的大数函数！