是否有河内塔的运行时间小于o一个解决方案（2 的 N 的）其中的 N 的是磁盘的数量移动？我的解决方案需要O（2 的 N 的）的时间。

Is there a solution for Towers of Hanoi whose running time is less than O(2n) where n is the number of disks to move? My solution takes O(2n) time.

另外，下面的解决方案是用递归。我们可以使用动态编程使用记忆化的概念来解决这个问题的一个较小的时间？

Also, the below solution is with recursion. Can we use Dynamic Programming with the concept of memoization to solve this in a lesser time?

public void towersOfHanoi(
        int num, 
        MyStack<Integer> from,
        MyStack<Integer> to, 
        MyStack<Integer> spare
) {
    if (num == 1) {
        int i = from.pop();
        to.push(i);
        System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName());
        return;
    }
    towersOfHanoi(num - 1, from, spare, to);
    towersOfHanoi(1, from, to, spare);
    towersOfHanoi(num - 1, spare, to, from);
}

MyStack 是一个扩展版本堆栈的Java类，增加了一个名称字段的访问。

MyStack is an extended version of Stack class in Java that adds a name field and accessor.

此外，有同样的问题，有没有什么变化？

Also, are there any variations of the same problem?

推荐答案

由于解决河内塔始终把2 ^ N - 1步......不，你不会找到一个更快的算法，因为它需要O（2 ^ n）的刚打印出的步骤，更不用说计算它们。

Given that solving Towers of Hanoi always takes 2^n - 1 steps...no, you're not going to find a faster algorithm, because it takes O(2^n) just to print out the steps, much less compute them.