Strange Towers of Hanoi题解

题意就是要求解出有n个盘子四个塔的汉诺塔问题。
三个塔的经典汉诺塔很好解。用sum[n]表示有n个盘子三个塔的答案，能得到如下递推式
d[n]=d[n-1]*2+1
表示先把n-1个盘子从1塔移到2塔，再把第n个盘子移到3塔，再把n-1个盘子从2塔移到3塔。
现在考虑4塔的情况。
用num[n]表示n个盘子四个塔的答案，先考虑前i个盘子，把这i个盘子从1塔移到2塔需要num[i]步，然后把剩下n-i个盘子从1塔移到4塔需要sum[n-i]步，再把前i个盘子从2塔移到4塔需要num[i]步，这样就能的到一个递推式
num[n]=min(num[i]*2+sum[n-i]) (i>=1 && i<=n)
这样，只要先处理出三塔情况下的答案，就可以递推出四塔情况下的答案。
代码如下

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int ans3[15],ans4[15];
int main()
{
    memset(ans4,0x3f,sizeof(ans4));
    ans3[1]=1;
    for(int i=2;i<=12;++i)
        ans3[i]=ans3[i-1]*2+1;
    ans4[1]=1;
    for(int i=2;i<=12;++i)
        for(int j=1;j<=i;++j)
            ans4[i]=min(ans4[i],ans4[j]*2+ans3[i-j]);
    for(int i=1;i<=12;++i)
        printf("%d\n",ans4[i]);
    return 0;
}