5. 最長回文子串
先枚舉長度len，再枚舉起始位置i
只能是連續(xù)子串能這樣遍歷题诵。
最長回文子序列還是要狀態(tài)轉(zhuǎn)移
暴力
從中間向兩邊擴散
class Solution {
public:
string longestPalindrome(string s) {
int len=0;
string res;
for(int k=0;k<s.size();k++){
int i=k,j=k+1;
while(i>=0 && j<s.size() && s[i]==s[j] )i--,j++;
if(j-i-1>len){
len=j-i-1;
res=s.substr(i+1,len);
}
i=k-1,j=k+1;
while(i>=0 && j<s.size() && s[i]==s[j] )i--,j++;
if(j-i-1>len){
len=j-i-1;
res=s.substr(i+1,len);
}
}
return res;
}
};
dp
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
if(!n)return "";
bool st[n][n];
int start=0,end=0;
for(int len=1;len<=n;len++){
for(int i=0;i+len-1<n;i++){
int j=i+len-1;
st[i][j] = (len==1 || len==2 || st[i+1][j-1]) && s[i]==s[j];
if(st[i][j] && j-i>end-start){
start=i;
end=j;
}
}
}
return s.substr(start,end-start+1);
}
};
