解决4座塔的hanoi塔问题，即有四座塔，不妨编号1～4,在塔一上有n个环套在上面，从上到小直径依次变大，每次可以选择将一个环从塔一移动到任何一座塔，但要保证直径大的环套在直径小的环的下面，询问将所有的环从塔一移动到塔四的最少方案数。
解
显然会联想到经典hanoi塔问题，即只有三座塔，不妨设(f_i)表示只有三座塔且有i个环套在塔一的最少将所有环移动到塔三的方案数，显然有
[f_i=f_{i-1}+1+f_{i-1}=2f_{i-1}+1
]
边界：(f_0=0)
含义即现将i-1个环从在三塔下塔一移动到塔二，再将最后一个在塔一的环移动到塔三，最后在三塔环境下移动第二座塔的i-1个环到塔三。
同样地类比设(g_i)为将i个环在4塔下从塔一移动到塔四的最少方案数，很难有
[g_i=min_{1leq k<i}{2g_k+f_{i-k}}
]
边界：(g_0=0)
含义即现将k个塔四塔环境下移动到塔二，剩下的塔在三塔环境下全部移动到第4塔，最后将塔二的k个环在4塔环境下移动到塔四。
之所以为什么是对的，我想这是我的未解之谜之一了。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define ll long long
using namespace std;
ll f[13],g[13];
template<class free>
il free Min(free,free);
int main(){
memset(g,0x3f,sizeof(g)),g[1]=1,g[0]=0;
for(int i(1),j;i<=12;++i){
f[i]=2*f[i-1]+1;
for(j=1;j<i;++j)
g[i]=Min(g[i],2*g[j]+f[i-j]);
printf("%lld
",g[i]);
}
return 0;
}
template<class free>
il free Min(free a,free b){
return a<b?a:b;
}