先復(fù)習(xí)一下動(dòng)態(tài)規(guī)劃的三個(gè)特征：
最優(yōu)子結(jié)構(gòu)：就是問題的最優(yōu)解包含子問題的最優(yōu)解，也就是可以通過子問題的最優(yōu)解麻汰，推導(dǎo)出問題的最優(yōu)解。
無后效性：再推倒后階段狀態(tài)的時(shí)候，只關(guān)心前面階段的狀態(tài)值彼哼，而不關(guān)心這個(gè)狀態(tài)是怎么推導(dǎo)過來的。
重復(fù)子問題：不同決策序列湘今，到達(dá)相同階段的時(shí)候敢朱，可能產(chǎn)生重復(fù)的狀態(tài)。
分析：
那我們回到最長回文子串的問題上來摩瞎，我們可以找到規(guī)律拴签，我們定義兩個(gè)指針i和j，代表字串在當(dāng)前字符串的位置旗们。f(i,j)代表當(dāng)前字串是否是回文串f(i,j) = (s[i] == s[j]) && f(i+1,j-1),并且當(dāng)j-i<3的時(shí)候,只需要比較s[i]和s[j]是否相等就可以了f(i,j) = (s[i] == s[j])蚓哩。
通過以上分析，最長回文子串問題滿足最優(yōu)子結(jié)構(gòu)（可以通過f(i+1,j-1)推導(dǎo)出f(i,j)）,滿足無后效性（只需要知道f(i+1,j-1)的值就可以了）上渴，重復(fù)子問題岸梨。
代碼：
代碼如下C++
string longestPalindrome(string s) {
int n = s.length(), left = 0, right = 0;
if (n==1) return s;
vector<vector<bool>> dp(n, vector<bool>(n,false));
for (int i=n-2; i>=0; i--){
dp[i][i] = true;
for (int j=i; j<n; j++){
if (j-i < 3){
dp[i][j] = (s[i] == s[j]);
}else{
dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
}
if (dp[i][j] && (right-left < j-i)){
right = j;
left = i;
}
}
}
return s.substr(left,right);
}
