LintCode: 汉诺塔问题

题目：汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在A，B，C三根柱子上，有n个不同大小的圆盘（假设半径分别为1-n吧），一开始他们都叠在我A上（如图所示），你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。
游戏中的每一步规则如下：
1. 每一步只允许移动一个盘子（从一根柱子最上方到另一个柱子的最上方）

2. 移动的过程中，你必须保证大的盘子不能在小的盘子上方（小的可以放在大的上面，最大盘子下面不能有任何其他大小的盘子)

图示：

思路：

lintcode把这道题目归类到回溯法里面了，汉诺塔问题主要还是一个经典的递归问题。

知乎上有关于它的一些讨论：https://www.zhihu.com/question/24385418

其实递归步骤可以看下图：

先把1,n-1移动到缓冲区上， 然后把最大的移动到目标C柱上，然后将B柱上的1,n-1移动到C柱上。

所以说一共就三步

1. 把 n-1 号盘子移动到缓冲区
2. 把1号从起点移到终点
3. 然后把缓冲区的n-1号盘子也移到终点

下面是使用Java实现的代码：

    public  List<String> result = new ArrayList<>();
    public  List<String> towerOfHanoi(int n) {
        move(n,"A","B","C");
        return result;
    }
    public  void move(int n, String from ,String buffer, String to){
        if(n==1){
            result.add("from "+from+" to "+to);
        }else{
            move(n-1,from,to,buffer);           // 将1- n-1 移动到buffer，即缓冲区
            result.add("from "+from+" to "+to); // 将n移动到目标柱子上
            move(n-1,buffer,from,to);           // 将1- n-1 移动到目标柱子上
        }
    }

    public static void main(String[] args) {
        System.out.println(towerOfHanoi(3));
    }

https://www.cnblogs.com/tgycoder/p/6063722.html