代码:
#include<iostream>
#include<cstring>
using namespace std;
int a[13],b[13];//a数组中存放三级汉诺塔步数,b数组即为答案
int main(){
memset(b,0x3f,sizeof(b));
b[1]=1;
for(int i=1;i<=12;i++)
a[i]=2*a[i-1]+1;
for(int i=1;i<=12;i++)
for(int j=1;j<i;j++)
b[i]=min(b[i],2*b[j]+a[i-j]);
for(int i=1;i<=12;i++)
cout<<b[i]<<endl;
return 0;
}
b需要DP(感觉很暴力,一点没有递推的感觉)求出:
b[i]=min(b[i],2*b[j]+a[i-j]);
b[j]表示的是上层的j个盘子到达目的地的次数(此时有4个柱子参与)
a[i-j]为剩下i-j个盘子的次数(此时就只有3个柱子参与,前j个占了一个柱子)
由于把前j个得挪回去,所以要把b[j]乘2;