给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

 

 

思路：

动态规划，dp[i][j]代表 i到j之间的串是否是一个回文串

dp[i][i]=true

dp[i][j]=s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];（将所有j<i的情况都置为true  是对越界的一种处理因此 dp[i][i+1]也满足这个条件）

    public String longestPalindrome(String s) {
		if (s.length() == 0)
			return "";
		int start = 0;
		int end = 0;
		boolean[][] dp = new boolean[s.length()][s.length()];
		// 把所有j<i的格式设置为true
		for (int i = 0; i < dp.length; i++)
			for (int j = 0; j < i; j++) {
				dp[i][j] = true;
			}

		int maxLen = 0;

		for (int i = s.length() - 1; i >= 0; i--) {
			dp[i][i] = true; // diagonal as true
			for (int j = i + 1; j < s.length(); j++) { // j是大于i的
				dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
				if (dp[i][j]) {
					if (maxLen < j - i) {
						maxLen = j - i;
						start = i;
						end = j;
					}
				}
			}
		}
		return s.substring(start, end + 1);
	}