汉诺塔问题

题目

开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，请实现一个函数打印最优移动轨迹。

给定一个int n，表示有n个圆盘。请返回一个string数组，其中的元素依次为每次移动的描述。描述格式为： move from [left/mid/right] to [left/mid/right]。

输入：1
返回：move from left to right

思路

• n 层汉诺塔问题，要解决的是
  • 把 1 ~ n -1 层圆盘从left 移动到 mid ，可以借助 right
  • 最后把第 n 层移动到 right
• n - 1 层汉诺塔问题，要解决的是
  • 把 1 ~ n - 2 层圆盘从 mid 移动到 left，可以借助的是 right
  • 最后把第 n - 1 层移动到 right
• n - 2 层汉诺塔问题，要解决的是
  • 把 1 ~ n - 3 层圆盘从 left 移动到 mid，可以借助的是 right
  • 最后把第 n - 2 层移动 right
• n - 3 层汉诺塔问题，要解决的是
  • 把 1 ~ n - 4 层圆盘从 mid 移动 left，可以借助的是 right
  • 最后把第 n - 3 层移动到 right
• ...

可以发现这是两个过程不断在反复循环，都是借助 right，来把临时的头上的一堆塔移动到 left / mid，再从 left / mid 移动最底下的圆盘到 right 中去

最后，如果只剩下一个了，直接把它从 left 移动到 right 去

思考这个问题的重点是，left mid 和 right 是三个相对概念位置，在每一次过程都是相对改变的

class Hanoi {
    public ArrayList<String> getSolution(int n) {
        ArrayList<String> list = new ArrayList<>();
        move(n, "left", "right", "mid", list);
        return list;
    }

    private void move(int n,
                      String from,
                      String to,
                      String help,
                      ArrayList<String> list) {
        if (n == 1) {
            list.add("move from" + from + " to " + to);
        } else {
            move(n - 1, from, help, to, list);
            list.add("move from" + from + " to " + to);
            move(n - 1, help, to, from, list);
        }
    }
}

总结

今天复习左神的递归与 dp 课