在见奇怪的汉诺塔

题目连接：https://www.acwing.com/activity/content/problem/content/330/

二刷，利用递推的思想来解决问题

code:

 1 //递推、dp思想
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define int long long
 5 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 6 const int N=15;
 7 int d[N];//三塔模式下的最小步数
 8 int f[N];//四塔模式下的最小步数
 9 signed main()
10 {
11     IOS;
12     d[1]=1;
13     for(int i=2;i<=N;i++)
14     {
15         d[i]=2*d[i-1]+1;//先考虑三塔模式的移动，即先将i-1根放在B上，第i根放在c上，再将i-1根放在C上
16     }
17     memset(f,0x3f,sizeof(f));
18     f[0]=0;
19     for(int i=1;i<=N;i++)
20     {
21         for(int j=0;j<i;j++)
22         {
23             f[i]=min(f[i],f[j]*2+d[i-j]);//先将前j根放在B上（四塔）,再将i-j放在d上（三塔），再将j根放在D上（四塔）
24         }
25     }
26     for(int i=1;i<=12;i++)
27     {
28         cout<<f[i]<<endl;
29     }
30     return 0;
31 }