647 回文子串
代码如下
func countSubstrings(s string) int { //dp[i][j]数组的含义是i-j这个范围的元素是否为回文串
dp := make([][]bool,len(s))
for i,_ := range dp {
dp[i] = make([]bool,len(s))
}
res := 0
for i := len(s)-1 ; i >= 0 ; i-- { 因为dp[i][j]是由dp[i+1][j-1] 推出来的，所以要重底向上，从左往右遍历
for j := i ; j < len(s) ; j++ { j从i的位置向后移动，i向前移动，这样保证能够始终j不小于i
if s[i] == s[j] { //如果两个元素相等
if j - i <= 1 { 并且两个元素相差小于1，即两个元素是同一个元素或者相差只有1 那么就必然是回文子串，结果加1
dp[i][j] = true
res++
}else if dp[i+1][j-1] == true { 如果两个元素的距离大于了1 ，那么就要判断dp[i+1][j-1] 是否为回文子串，如果 dp[i][j] 是回文子串，那么就说明这个也是回文子串
dp[i][j] = true
res++
}
}else {
dp[i][j] = false 如果两个元素不相同则不是回文子串
}
}
}
return res
}
516 最长回文子序列
代码如下
func longestPalindromeSubseq(s string) int { dp[i][j]的含义是i-j这个范围的最长回文子序列的长度
dp := make([][]int,len(s))
for i := 0 ; i < len(s) ; i++ {
dp[i] = make([]int,len(s))
dp[i][i] = 1 下标相同，则是回文子序列，且长度为1
}
for i := len(s)-1 ; i >= 0 ; i--{
for j := i+1 ; j < len(s) ; 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][len(s)-1]
}
func max(a,b int) int {
if a > b {
return a
}else {
return b
}
}
