4.2（动态规划）

4.2

Lc.5.最长回文串

class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;boolean[][] dp = new boolean[len][len];for (int i = 0; i < len;i++) {dp [i][i] = true;//长度为1的都是回文}char[] charArray = s.toCharArray();/*s 是一个字符串（String 类型）.toCharArray() 是 String 类的方法功能：把字符串 拆分成字符数组（每个字符一个格子）*/for (int L = 2; L <= len; L++) {for (int i = 0; i < len; i++) {int j = L + i - 1;if (j >= len) {break;//右边届越界}if (charArray[i] != charArray[j]) {dp[i][j] = false;}else if (j - i < 3) {dp[i][j] = true;}else {dp[i][j] = dp[i + 1][j - 1];//要求里面也是回文}if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);//从原字符串 s 里截取一段子串}
}