Leetcode 5 Longest Palindromic Substring DP
Given a string s, return the longest palindromic substring in s.
Solution
设 \(dp[i][j]\) 表示字串 \(s[i,...,j]\) 是否为回文串。初始化时，每个单独的字符本身就是回文串；长度为2的串只要首尾相同，也是回文串；长度 \(\geq 3\) 时，只有满足：
\[dp[i+1][j-1]\ \&\&\ s[i]=s[j] \]此时 \(dp[i][j]\) 也就是回文串。因此循环内侧的 \(i\) 时，应倒序遍历
点击查看代码
class Solution {
private:
bool dp[1003][1003];
int MAX = -1;
int ansl, ansr;
public:
string longestPalindrome(string s) {
int n = s.length();
for(int i=0;i=0;i--){
if(i+1==j){
if(s[i]==s[j])dp[i][j] = true;
else dp[i][j] = false;
}
else{
if(s[i]==s[j] && dp[i+1][j-1])dp[i][j] = true;
else dp[i][j] = false;
}
if(dp[i][j]){
if(MAX