以下是我对LZ推理式的一些补充，写得较详细，希望给后来人一点帮助。
首先研究一两个基本的问题：
1)	空杆上环K的步骤：
上1~K-1环  下1~K-2环  上环K(1步) 此时杆上存在K、K-1两个环,现在要保证K环之前无环,则要下K-1环(但因为递归K-2环则会出现于杆上),此时要解决的问题是”把只上有环K-1的杆变为空杆”(环K-1之后是否有环对此无影响);
2)	把只有环K的杆变为空杆：
上1~K-1环  下1~K-2环  下K环(1步)  问题转化为”把只有环K-1的杆变为空杆”的子问题;
3)	由以上看来,似乎上1~K-1环和下1~K-1环都还要转化为子问题。下1~K-1环：下K环,下K-1环,……;而上1~K-1环则为上环K(但此时K-1环也在杆上,不必挪去),上环K-2,上环K-4……
由这三点看问题十分复杂。难于推理。但这里有一个隐蔽点没有发现,它关系互整到的推理。
来看下问题1)。要下空杆上的环K并使之前全部为0则必须要1~K-2环不在杆上,而K-1环在杆上方可操作。注意！比较只有环K的杆和可以下环K时的状态,其实以上步骤可以述为：
在环K之前上环K-1并使之前全部为0;下环K。
而”在环K之前上环K-1”和”在空杆上上环K-1”其实是同一个问题,因为环K对上环K-1的过程没有任何关联。容易想到”空杆上环K”和”只有环K的杆下环K”之间有什么关联？
Up(k):空杆上环K并使之前全部为0：上环K-1并使之前全部为0  上环K  下环K-1并使之前全部为0;
Down(k):只有环K的杆下环K并使之前全部为0：上环K-1并使之前全部为0  下环K  下环K-1并使之前全部为0。
可以看到Up(k) = Down(k),设为S[k];
又可以看到S[k] = Up(k-1) + 1 + Down(k-1) = 2*S[k-1] + 1,
=>S[k] + 1 = 2 * (S[k-1] + 1)
=>(S[k] + 1) / (S[k-1] + 1) = 2.
则S[k] + 1 = (S[1] + 1) * 2^(k – 1) => S[k] = (1 + 1) * 2^(k – 1) -1 = 2^k - 1.
好,下面再看推理第三条：
a[n] = 1,  g[n-1](使环n-1为1且之前的环全部为0,这和我的推理不同,因为环n-1之前可能存在环)下环n(1步)此时只有环n-1在杆上,问题转化为”下环n-1并使之前全部为0”的问题,
即S[n-1] = 2^(n-1) – 1,但之前下环n是一步,所以总步数为：
g[n-1] + 1 + 2^(n-1) – 1 = g[n-1] + 2^(n-1).
同理可推证第四条。
另外，我希望大家注意的是要考虑结果为0的情况，这时输出为0就可以了，我就是因为这种情况没有输出而费了很长时间才AC的。