package main
func max(a, b int) int {
if a > b {
return a
}
return b
}
func countSubstrings(s string) int {
n := len(s)
dp := make([][]bool, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
}
num := 0
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] {
// 如果j和i相同，字符串等a是回文，如果j和i之差等于1 ，字符串等aa也是回文
if j-i <= 1 {
dp[i][j] = true
num++
//相差大于1看dp[i + 1][j - 1]是否为true，为true也是回文
} else if dp[i+1][j-1] {
dp[i][j] = true
num++
}
}
}
}
return num
}
func longestPalindromeSubseq(s string) int {
n := len(s)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
dp[i][i] = 1
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
//左右两边相等加2
dp[i][j] = dp[i+1][j-1] + 2
} else {
//不相等取左右两边最大值
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
}
}
}
return dp[0][n-1]
}