647 回文字串
func countSubstrings(s string) int {// 动规五部曲// dp[i][j] 表示s[i: j+1] 区间是否是一个回文// if s[i] == s[j] {if i-j <= 1 || dp[i+1][j-1] == true { dp[i][j] == true}}// 初始化为false// 从下往上，从左往右// printvar count intvar dp = make([][]bool, len(s))for i, _ := range dp {dp[i] = make([]bool, len(s))}for i:=len(s)-1; i>=0; i-- {for j:=i; j<len(s); j++ {if s[i] == s[j]{if j-i<=1 || dp[i+1][j-1] == true {dp[i][j] = truecount++}}}}//fmt.Println(dp)return count
}
516 最长回文子序列
func longestPalindromeSubseq(s string) int {// 647 回文字串变体，只用统计最长字串即可// dp[i][j] 表示s[i: j+1] 最长回文子串长度// s[i] != s[j] {dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i][j-1])} // 删除i， 删除j， 两个都删除// s[i] == s[j] {dp[i+1][j-1] + 2} // 去除首位之后的最长字串 + 两个字符长度// 初始化为0 , 多初始化一行一列// 递推来自三个方向，左下，左，下，所以遍历顺序从下往上，从左往右// printvar maxlen intvar dp = make([][]int, len(s) + 1)for i, _ := range dp {dp[i] = make([]int, len(s) + 1)}for i:=len(s); i>=0; i-- {for j:=i; j<len(s); j++ {if s[i] == s[j]{if i == j {dp[i][j+1] = dp[i+1][j] + 1}else {dp[i][j+1] = dp[i+1][j] + 2}} else {dp[i][j+1] = max(dp[i+1][j], max(dp[i+1][j+1], dp[i][j]))}if dp[i][j+1] > maxlen {maxlen = dp[i][j+1]}}}//fmt.Println(dp)return maxlen
}
