最长回文子串-动态规划解法

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

func longestPalindrome(s string) string {
	//根据字符长度初始化一个二维数组，下标对应字幕的位置
	dp := make([][]bool, len(s))
	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
	}
	ans := ""
	for i := 0; i < len(s); i++ {
		for k := 0; k <= i; k++ {
			//前后字符相同 && 中间的字符也是回文串
			dp[i][k] = s[i] == s[k] && (i-1 < k+1 || dp[i-1][k+1])
			if dp[i][k] && i-k+1 > len(ans) {
				ans = s[k : i+1]
			}
		}
	}
	return ans
}