【BM73】动态规划-最长回文子串

求解代码

publicintgetLongestPalindrome(StringA){if(A==null||A.length()==0){return0;}intn=A.length();char[]str=A.toCharArray();intmax=1;boolean[][]dp=newboolean[n][n];for(inti=0;i<n;i++){dp[i][i]=true;}for(inti=1;i<n;i++){for(intj=0;j<i;j++){if(str[i]!=str[j]){dp[j][i]=false;}else{if(i-j<=1){dp[j][i]=true;}else{dp[j][i]=dp[j+1][i-1];}if(dp[j][i]){max=Math.max(max,i-j+1);}}}}returnmax;}

小贴士

1.dp[j][i]表示子串A[j..i]（闭区间）是否为回文，必须保证j ≤ i

2. 判断规则：

• 首尾不等 → 非回文
• 首尾相等 + 长度≤2 → 必回文
• 首尾相等 + 长度 > 2 → 看中间子串是否回文