分析：
对于三柱汉诺塔问题，我们已经熟知步骤数最优解为
2
i
−
1
2^{i}-1
2i−1,其中 i 为盘子个数。
对于四柱以上的问题，我们将柱子分为三类，起点柱Start，辅助柱Buf，终点柱End，三柱情况时，我们总想着将前n - 1个盘从Start借助End移动到Buf，然后将第 n 个盘从Start移到End，最后将Buf柱上的n - 1个盘借助Start移到End，这就找到了递推关系：
S
t
e
p
s
(
n
)
=
2
∗
S
t
e
p
s
(
n
−
1
)
+
1
Steps(n) = 2*Steps(n-1)+1
Steps(n)=2∗Steps(n−1)+1
对于三柱问题，我们将前n-1盘移到Buf是唯一的选择，对于四柱以上的问题，我们可以移前n-1或者前n-2等等，哪个最佳呢？这就需要动态规划了。
思路：
这里提供Frame算法：
由于不知道哪个 r 使得移动前 n - r 个盘是最优解，我们需要算出所有可能性再取最小值。
（1）首先把前 n - r 个盘移从Strat移到Buf上，此时可用柱数为 m ，步骤数是 S t e p s ( m , n − r ) Steps(m,n-r) Steps(m,n−r)
（2）再将剩下的 r 个盘从Start移到End上，由于上述步骤占用了1根柱子步骤数是 S t e p s ( m − 1 ， r ) Steps(m - 1，r) Steps(m−1，r)
（3）最后将第一步的 n - r 个盘从Buf移到End上，虽然End柱被占用，但其中的盘均比这 n - r 个大，故可用柱子数仍为 m ，步骤数是 S t e p s ( m ， n − r ) Steps(m，n-r) Steps(m，n−r)
（4）依据上边规则求出所有 r （ 1 ≤ r ≤ n ） r（1≤r≤n） r（1≤r≤n）情况下步数，取最小值得最终解。
因此Frame算法的递归方程如下：
S t e p s ( m , n ) = m i n ( 2 ∗ S t e p s ( m , n − r ) + S t e p s ( m − 1 , r ) ) ， （ 1 ≤ r ≤ n ） 。 Steps(m,n)=min(2*Steps(m,n-r)+Steps(m-1,r))，（1≤r≤n）。 Steps(m,n)=min(2∗Steps(m,n−r)+Steps(m−1,r))，（1≤r≤n）。
于是有下列代码：
#include <stdio.h>
#include <math.h>
long long min_steps(int m,int n);
long long min(long long a,long long b);
int main() {
int m,n;
scanf("%d %d",&m,&n);
printf("%lld\n",min_steps(m,n));
}
long long min_steps(int m,int n) {
if(n == 0) return 0;//若盘子数为0，无论柱子数为多少，移动步数都是0
if(n == 1) return 1;//若盘子数为1，无论柱子数为多少，移动步数都是1
if(n == 2) return 3;//若盘子数为2，无论柱子数为多少，移动步数都是2
if(m == 3) return (long long)pow(2,n) - 1;//若柱子数为3，就是经典的三柱汉诺塔问题
else if(m > 3){//四柱及以上汉诺塔问题
long long mini = (long long)pow(2,30);//预设一个比较大的值，方便下面取最小值不出错
for(int i = 1;i <= n;i ++) {
mini = min(mini,2*min_steps(m,n-i)+min_steps(m-1,i));
}//动态规划
return mini;
}
}
long long min(long long a,long long b) {
if(a <= b) return a;
else return b;
}