算法竞赛进阶指南：奇怪的汉诺塔（Python）

题目描述：

汉诺塔问题，条件如下：

1、这里有 A、B、C和 D 四座塔。

2、这里有 n 个圆盘，n 的数量是恒定的。

3、每个圆盘的尺寸都不相同。

4、所有的圆盘在开始时都堆叠在塔 A 上，且圆盘尺寸从塔顶到塔底逐渐增大。

5、我们需要将所有的圆盘都从塔 A 转移到塔 D 上。

6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。

请你求出将所有圆盘从塔 A 移动到塔 D，所需的最小移动次数是多少。

数据范围

1≤n≤12

 解题思路： 

设Three[n]表示求解n盘3塔问题的最小步数

递推式：Three[n] = 2 * Three[n-1] + 1

含义：即把前n-1个盘子从A柱移到B柱，然后把A柱上剩的那一个盘子移动到C柱，最后把B柱上的那n-1个盘子移动到C柱上

设Four[n]表示求解n盘4塔问题的最小步数

递推式：Four[n] = min(2 * Four[i] + Three[n - i])

含义：

初始化：Four[1] = 1(一个盘子在4塔模式下移动到D柱需要1步)
先把i个盘子在4塔模式下移动到B柱，
然后把n-i个盘子在3塔模式下移动到D柱（因为不能覆盖到B柱上，就等于只剩下A、C、D柱可以用）
最后把i个盘子在4塔模式下移动到D柱
考虑所有可能的i取最小值，即得到上述递推公式

Python3代码 

 
Three = [0] * 15
Four = [float('inf')] * 15
 
Three[1] = 1
# 当只有三根柱子时 移动i个盘子所需要的次数
for i in range(2,13) :
    Three[i] = Three[i-1] * 2 + 1
 
# 当有四根柱子时 移动i个盘子所需要的次数
Four[0] = 0
for i in range(1,13) :
    for j in range(i) :
        Four[i] = min(Four[i],Four[j]*2+Three[i-j])
        
for i in range(1,13) : print(Four[i])