【题目描述】给定A 、 B 、 C A、B、CA、B、C三根足够长的细柱在A AA柱上放有2 n 2n2n个中间有孔的圆盘共有n nn个不同的尺寸每个尺寸都有两个相同的圆盘注意这两个圆盘是不加区分的现要将这些圆盘移到C CC柱上在移动过程中可放在B BB柱上暂存。要求： 1 11每次只能移动一个圆盘； 2 A 、 B 、 C 2A、B、C2A、B、C三根细柱上的圆盘都要保持上小下大的顺序；设A

【样例输入】 2

【样例输出】 7

【样例说明】 当n=2时，共有4个圆盘，需要移动7次才能将它们从A柱移到C柱：

1. 将编号为1的圆盘从A移到B；
2. 将编号为2的圆盘从A移到C；
3. 将编号为1的圆盘从B移到C；
4. 将编号为3的圆盘从A移到B；
5. 将编号为1的圆盘从C移到A；
6. 将编号为2的圆盘从C移到B；
7. 将编号为1的圆盘从A移到C。

【数据说明】 对于100%的数据，1≤n≤20。

【题目分析】 问题描述中已经给出了最优解，因此可以使用递归的方法进行求解。设函数 $f(n)$ 表示将 $n$ 个圆盘从柱子 $A$ 移动到柱子 $C$ 的最少步数，将 $n$ 个圆盘从柱子 $A$ 移动到柱子 $C$ 的最优方案可以分解为以下三个步骤：

1. 将 $n-1$ 个圆盘从柱子 $A$ 移动到柱子 $B$；
2. 将编号为 $n$ 的圆盘从柱子 $A$ 移动到柱子 $C$；
3. 将 $n-1$ 个圆盘从柱子 $B$ 移动到柱子 $C$。

因此，可以得到递推式 $f(n)=2f(n-1)+1$，初始条件为 $f(1)=1$。注意，每次移动时需要保持圆盘上小下大的顺序。如果将编号为 $n$ 的圆盘从某个柱子移动到另一个柱子，那么它下面的所有圆盘也需要一起移动。

具体实现时，可以使用递归函数进行求解。在递归函数中，将参数分别设为起点、终点和中转点对应的柱子编号，以及待移动的圆盘数量。在递归的过程中，按照上述步骤进行移动，并统计移动步数。递归终止条件是只有一个圆盘需要移动，此时直接将圆盘从起点移动到终点即可，移动步数为1。

注意，由于圆盘的编号是从小到大排列的，因此实际上可以用一个二维数组 $disk[i][j]$ 表示第 $i$ 根柱子上编号为 $j$ 的圆盘的位置（$0$ 表示该位置没有圆盘）。这样在移动圆盘时，只需要更新相应位置的值即可。同时，可以使用一个变量 $cnt$ 统计移动步数。

【时间复杂度】 递归深度为 $O(n)$，每次递归的时间复杂度为 $O(n)$（需要将 $n$ 个圆盘从一个柱子移动到另一个柱子），因此总时间复杂度为 $O(n^2)$。

【空间复杂度】 需要使用一个二维数组 $disk$ 存储圆盘的位置，因此空间复杂度为 $O(n^2)$