对于三根柱子的汉诺塔
若有n个盘子在A柱,想要将所有盘子从A柱移动到C柱,所需要的最少操作数为2^n-1
d[1]=1;
// i代表的是盘子数量,d是最少得操作数
for(int i=2;i<=n;i++)
{
d[i]=1+d[i-1] * 2;
}
首先将前n-1个盘子从A柱移动到B柱
最后一个盘子从A柱移动到C柱
再将n-1个盘子从B柱移动到C柱
若有四根柱子
要想求n个盘子从A柱移动到D柱的最少操作数,则在三根柱子的基础上计算
代码如下:
int f[N];
// f[i] 是四根柱子,移动i个盘子的最小操作数
for(int i=2;i<=n;i++)
{
/*
先移动j个盘子到B柱(四根柱子的情况下移动的
再将剩余的i-j个盘子从A柱移动到D柱(三根柱子)
最后将j个盘子从B柱移动到D柱(四根柱子)
*/
for(int j=0;j<=i;j++)
{
f[i]=min(f[i],f[j] * 2 + d[i-j] );
}
}