浅谈 多柱汉诺塔问题

众所周知，汉诺塔问题很经典。
这里用DP可以解决$n$个塔$m$个柱子的移动次数问题
当然想要输出步骤也可以

我们回忆一下只有三根柱子的情况：

先把$n−1$个盘子移到第二根柱子上，再把剩下的那一个盘子移到第三根柱子，最后再把$n−1$个盘子移到第三根柱子上。
如果我们用$Fn$来表示移动（三根柱子时）$n$个盘子的最小步数，按照上面的叙述，则有：
$Fn=2×Fn−1+1$
这样一个递推式，不写出它的通项公式是$2n−1$。
我们再考虑四根柱子的情况。
我们按照同样的思路，考虑到底是先留几个盘子，先移几个盘子。我们设留下$r$个盘子，移动$n−r$个盘子把他们放到第三根柱子上，再用剩下的三根柱子把移动剩下的r个盘子移动到第4根柱子上。我们同样用$Fn$来表示移动n个盘子的最小步数，就有这样一个式子：
$Fn=min(2×Fn−r+2r−1)$
同样的，如果定义$dp[i][j]$为把i个盘子移动到j根柱子的最小步数，就有：
$dp[i][j]=min(2×dp[i−r][j]+dp[r][j−1]),1<=r<=i$
关于初值，无疑dp数组要赋+inf，对于边界，也就是$n=1,m=1,n=2,m=2$的情况也要分别计算

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
long long f[70][70];
int main() 
{
    freopen("hanoi.in","r",stdin);
    freopen("hanoi.out","w",stdout);
    memset(f,-1,sizeof(f));
    for (int i=1;i<65;++i) 
    f[1][i]=1;
    for (int i=2;i<64;++i) 
    {
        for (int j=3;j<=i+1;++j)
        for (int k=1;k<i;++k) 
        {
            if (f[k][j]==-1||f[i-k][j-1]==-1) continue;
            long long temp=(f[k][j]<<1)+f[i-k][j-1];
            if (f[i][j]==-1||f[i][j]>temp) f[i][j]=temp;
        }
        for (int j=i+2;j<65;++j) f[i][j]=f[i][j-1];
    }
    scanf("%d%d",&n,&m);
    printf("%lld\n",f[n][m]);
    return 0;
}