我最近正在解决河内塔的问题。我使用“分而治之”策略来解决此问题。我将主要问题分为三个较小的子问题，因此产生了以下重复发生。
T（n）= 2T（n-1）+1
解决这个问题导致
O（2 ^ n）[指数时间]
然后我尝试使用记忆技术来解决它，但是这里空间的复杂度也是指数级的，堆空间很快用完，对于较大的n来说，问题仍然无法解决。
有没有一种方法可以在不到指数时间内解决问题？什么时候可以解决问题的最佳时间？
这取决于您“已解决”的意思。具有3个钉子和n磁盘的河内塔问题需要采取2**n - 1行动解决，因此，如果要枚举举动，显然不能比O(2**n)列举k事情做得更好O(k)。
n
2**n - 1
O(2**n)
k
O(k)
另一方面，如果您只想知道所需的移动次数（无需枚举），则计算2**n - 1速度会更快。
同样值得注意的是，可以通过O(n)以下方式（空间disk1最小的磁盘）来反复进行移动枚举（这是最小的磁盘）：
O(n)
disk1
while true: if n is even: move disk1 one peg left (first peg wraps around to last peg) else: move disk1 one peg right (last peg wraps around to first peg) if done: break else: make the only legal move not involving disk1
