汉诺塔问题 Tower of Hanoi

有 A,B,C 三根柱子，A 上面有 n 个盘子，我们想把 A 上面的盘子移动到 C 上，但是要满足以下三个条件：

• 每次只能移动一个盘子;

• 盘子只能从柱子顶端滑出移到下一根柱子;

• 盘子只能叠在比它大的盘子上。
  

• n = 1 时，直接把盘子从 A 移到 C；

• n > 1 时，
  先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
  再将最大的盘子从 A 移到 C；
  再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。

作者：z1m
链接：https://leetcode-cn.com/problems/hanota-lcci/solution/tu-jie-yi-nuo-ta-de-gu-shi-ju-shuo-dang-64ge-pan-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        movePlate(A.size(), A, B, C);
    }

    private void movePlate(int num, List<Integer> origin, List<Integer> aux, List<Integer> target) {
        if (num == 1) {
            // 只剩一个盘子时，直接移动即可
            // origin.size() - 1 表示最下面的元素 下标
            target.add(origin.remove(origin.size() - 1));
            return;
        }

        movePlate(num - 1, origin, target, aux);

        target.add(origin.remove(origin.size() - 1));

        movePlate(num - 1, aux, origin, target);
    }