PAT A1030 動態規劃
這道題是動態規劃幾大問題的其中一種,為最長迴文子串問題;
動態規劃個人來說,覺得最重要的就是建立狀態轉移方程。對於方程變數,我認為最重要的是有幾個構成的關鍵變數;
對於這道題,我們著手於i~j個字元,所以關注點在於i和j,所以我們建立一個二維矩陣來儲存動態規劃途中的計算值。對於dpi,其值為1時,意為i-j的字串是迴文子串,為其他值則不是;
對於狀態轉移方程,我們可以這樣想:對於一個迴文子串,其子串也是迴文子串,所以就有方程轉移的定律:
dpi=dpi+1
接下來就是如何遍歷;
對於遍歷,我們一定要保證從邊界開始,並且現有計算狀態必須建立在已有建立狀態之上。由於轉換方程的特殊性,i,j兩個座標都像兩邊擴散,所以我們可以根據L,也就是子串的長度來進行計算;
先將單個字元相應的值置為1,然後L=2.....至L=n;在途中記錄子串的長度;
程式碼如下所示:
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<cstring> #include<string> using namespace std; const int maxn=1010; string data; int matrix[maxn][maxn]; int main(){ getline(cin,data); int len=data.size(); for(int i=0;i<len;i++){ matrix[i][i]=1; } int ans=1; for(int i=1;i<len;i++){ if(data[i-1]==data[i]){ matrix[i-1][i]=1; ans=2; } } for(int L=3;L<=len;L++){ for(int i=0;i+L-1<len;i++){ int j=i+L-1; if(data[i]==data[j]&&matrix[i+1][j-1]==1){ matrix[i][j]=1; ans=L; } } } printf("%d\n",ans); system("pause"); return 0; }