題目鏈接：點擊查看

題目大意：繼承經典的n個盤子三座塔的漢諾塔問題，現在問對于n個盤子四座塔的升級版漢諾塔問題，對于n=1~12的答案分別是多少

題目分析：首先分析三座塔的情況，對于第n個盤子而言，我們需要先將上面n-1個盤子先從A柱子放到B柱子上去，再將第n個盤子放到C柱子上去，最后再將B柱子上的n-1個盤子轉移到C柱子上就好了，狀態轉移方程也很好寫，設dp1[i]為轉移i個盤子所需要的步數，那么上述的過程可以描述為dp[i]=dp[i-1]+1+dp[i-1]=dp[i-1]*2+1

現在我們再來分析一下對于四座塔的情況，因為對于三座塔而言，我們只能將n拆成n-1和1，所以轉移方程也就是一個簡單的等式關系，而四座塔的情況，有兩個塔可以輔助完成轉移，也就是說一開始我們可以將j個盤子從A柱子放到B柱子上去（四塔移動），然后再將n-j個盤子從A柱子放到D柱子上去（三塔移動），最后將j個盤子從B柱子放到D柱子上去（四塔移動），因為我們保證了分成的兩堆盤子j和n-j一定是連續的序號，所以不妨設dp2[i]代表在四座塔的情況下轉移i個盤子所需要的最小步數，那么轉移方程也就很好寫了：dp2[i]=min(2*dp2[j]+dp1[i-j])，這樣就能遍歷所有可行情況從而找到最優答案了，因為我們在處理第1個盤子到第j個盤子的時候，是在處理四座塔的漢諾塔問題，所以需要的步數是dp2[i]，然后再處理第j+1~n個盤子的時候，剛才放1~j的那個柱子已經不能用了，所以此時面對的是三座漢諾塔問題，這樣一來dp2的更新就需要借助dp1和dp2的前置狀態了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;LL dp1[20],dp2[20];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);memset(dp2,inf,sizeof(dp2));//因為要維護最小值，所以初始化dp2為無窮大dp1[1]=dp2[1]=1;//維護邊界:轉移1個盤子的最小步數都是1步for(int i=2;i<=12;i++)//轉移dp1dp1[i]=2*dp1[i-1]+1;for(int i=2;i<=12;i++)//轉移dp2for(int j=1;j<i;j++)dp2[i]=min(dp2[i],2*dp2[j]+dp1[i-j]);for(int i=1;i<=12;i++)printf("%lld\n",dp2[i]);return 0; }

總結

以上是生活随笔為你收集整理的POJ - 1958 Strange Towers of Hanoi(线性dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。