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
// 从下往上,从左往右
// print
var count int
var 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] = true
count++
}
}
}
}
//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 , 多初始化一行一列
// 递推来自三个方向,左下,左,下,所以遍历顺序从下往上,从左往右
// print
var maxlen int
var 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
}
标签:int,随想录,maxlen,647,最长,dp,回文
From: https://www.cnblogs.com/zhougongjin55/p/18389962