说是递推，其实也算是个DP吧。
就是4塔的汉诺塔问题。
考虑三塔：先从a挪n-1个到b，把最大的挪到c，然后再把n-1个从b挪到c，所以是
f[i] = 2 * f[i-1] + 1;
那么4塔类似：
先在4塔模式下挪j个到b，然后在三塔模式下挪n-j个到d，然后再在4塔模式下挪j个到d。
故状态转移方程：
d[i] = min(2 * d[j] + f[n-j]) ,其中1 <= j < n
初始条件：f[n]与d[1] = 1;
然后就没有然后了。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = ,INF=0x7f7f7f7f;
int f[N],d[N];
int main()
{
f[]=d[]=;
f[]=d[]=;
for(int i=;i<=;i++) {
f[i]=*f[i-]+;
}
for(int i=;i<=;i++)
{
int temp=INF;
for(int j=;j<i;j++)
temp=min(temp,*d[j]+f[i-j]);
d[i]=temp;
}
for(int i=;i<=;i++)
printf("%d\n",d[i]); return ;
}
AC代码