题目连接: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 }
原文链接: https://www.cnblogs.com/LQS-blog/p/17022274.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/309385
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!