从三汉诺塔问题到四汉诺塔问题

三汉诺塔问题

• 如果是三汉诺塔问题，那么我们别无选择，唯一解就是利用除了初始盘之外的两个盘子把前i-1个碟子移到中间盘上面去，然后我们把最下面的第i个盘子移到目标盘上，然后我们再继续将中间盘上面摆着的剩下的前i-1个盘子利用初始盘和目标盘两个盘子全部移到目标盘上，这个过程其实就是d[i]=d[i-1]+1+d[i-1]
• 因此，三汉诺塔问题的每一个汉诺塔其实都是由唯一解递推而来。

四汉诺塔问题

• 四汉诺塔问题的话，我们就多了许多的选择，我们可以将前j个碟子利用除了初始盘之外的三个盘子移动到第二盘上面去，然后再将初始盘上最下面的i-j个盘子利用除了初始盘和第二盘之外的两个盘子移动到目标盘上，最后再将第二盘上的j个盘子利用除了第二盘之外的三个盘子移动到目标盘上面去，这个过程其实就是f[i]=f[j]+d[i-j]+f[j]
• j的选择有i种，所以每一个f[i]其实都有j种可能，我们要求的是最小值也就是最优解，所以我们要在这j种情况种取最小值

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 15;
int d[N],f[N];
int main()
{
    for(int i=1;i<=12;i++)d[i]=d[i-1]*2+1;
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=12;i++)
    {
        for(int j=0;j<i;j++)
        {
            f[i]=min(f[j]+d[i-j]+f[j],f[i]);
        }
        cout<<f[i]<<endl;
    }
    return 0;
}