- 题目描述
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。 你需要原地修改栈。 示例1: 输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0] 示例2: 输入：A = [1, 0], B = [], C = [] 输出：C = [1, 0] 提示: A中盘子的数目不大于14个。
- 解法：分治递归
首先我们知道汉诺塔问题是一个很典型的递归案例。
我们解决一个只有3个盘子的汉诺塔，首先想到的是将A中[2,1,0]，2上面的1和0通过C移动到B，然后再直接将2从A移动到C，然后我们再将[1,0]从B通过A移动到C。
同理，有4个盘子的汉诺塔，我们将A上的[3,2,1,0]，最上面3个盘子[2,1,0]，通过C移动到B，然后再将3移动到C，再将B上的[2,1,0]通过A移动到C
..............
这样，我们就逐渐将A柱子上层数很高(假设为n)的汉诺塔的n-1层通过中间柱子C移动到柱子B，再通过A将n-1层移动到C。
这样是不是就找到了规律。
这其实就是一种分治思想：将问题分为若干更小规模的部分，通过解决每一个小规模问题，并将结果汇总得到原问题的解。
但是对于递归问题，真的不要想太多，要宏观地去看，要先抓住最小规模是什么，然后再找到减少规模的因子，然后找到递归的条件，直接递归就好了。
class Solution: def hanota(self, A: List[int], B: List[int], C: List[int]) -> None: """ Do not return anything, modify C in-place instead. """ n = len(A) self.move(n, A, B, C) def move(self, n, A, B, C): if n == 1: C.append(A.pop()) return else: self.move(n-1, A, C, B) #把n-1个盘子借助C移动到B C.append(A.pop()) self.move(n-1, B, A, C) #把B上的n-1个盘子，借助A移动到C