找到字符串s中的最长回文子串。
动态规划：将问题分解为子问题。
在本题中 状态转移方程为：P(i,j)=P(i+1,j−1)∧(Si==Sj) //∧求交集，相当于java中的 &&
边界条件:
P(i,i)=true
P(i,i+1)=(Si==Si+1)
public class Q5 { public String longestPalindrome(String s) { int n = s.length(); boolean[] [] dp = new boolean[n][n]; //dp[i][j] 表示子串s[i..j]是否为回文子串 String ans = ""; //实际上是按斜对角线填充dp表的上半部分 for (int len = 0; len < n; len++) { for (int i = 0; i+len < n; i++) { int j = i+len; if (len == 0) { //单个元素的一定为true dp[i][j] = true; }else if (len == 1) { dp[i][j] = (s.charAt(i) == s.charAt(j)); }else { //动态规划 --分解为更小的问题dp[i+1][j-1]; dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]); } if (dp[i][j] && len+1 >ans.length()) { //更新ans ans = s.substring(i,i+len+1); } } } return ans; } }
