如何计算一秒钟内任意n <= 600 的最短加法链（sac）？

笔记

这是本月有关Codility的编程竞赛。

加法链在数值上非常重要，因为它们是计算x ^ n（通过连续乘法）的最经济的方法。

克努斯的《计算机编程艺术》，第2卷，《半数值算法》很好地介绍了加法链和一些有趣的属性，但是我没有找到任何能够满足严格性能要求的东西。

我尝试过的（扰流板警报）

首先，我构造了一个（高度分支的） 树 （以1-> 2->（3-> …，4->
…）开始），这样对于每个节点n，从根到n的路径是n的一个囊。但是对于> 400的值，运行时间与煮咖啡的时间相同。

然后，我使用该程序找到了
一些有用的属性，以减少搜索空间
。这样一来，我就可以在煮咖啡的同时建立多达600种解决方案。但是对于n，我需要计算最多n的所有解。不幸的是，codility也会测量类初始化的运行时…

由于问题可能是NP困难的，因此我最终
对查找表进行 了 硬编码 。但是，由于codility要求 构造
囊，所以我不知道他们是否想到了查找表，因此我感到肮脏且像作弊者。因此，这个问题。

更新资料

如果您认为要使用硬编码的完整查找表，是否可以提出一个理由，为什么您认为完整的计算/部分计算的解决方案/启发式方法不起作用？