2021-02-08：給定一個(gè)字符串str，請問這個(gè)字符串的最長回文子序列長度是多少？
福哥答案2021-02-08：
自然智慧即可。
1.原序列和反序列求公共子序列。無代碼。
2.遞歸。有代碼。
3.動(dòng)態(tài)規(guī)劃。有代碼。
根據(jù)動(dòng)態(tài)規(guī)劃表，dp[i][j]取【左邊】，【下邊】，【左下邊】或者【左下邊+2】）的最大值。
【左下邊】還是【左下邊+2】？i==j,取【左下邊+2】；i!=j，取【左下邊】。
代碼用golang編寫，代碼如下：
package main
import "fmt"
func main() {
ret := longestPalindromeSubseq("bbbabbbb")
fmt.Println("遞歸：", ret)
ret = longestPalindromeSubseq2("bbbabbbb")
fmt.Println("動(dòng)態(tài)規(guī)劃：", ret)
}
//遞歸
func longestPalindromeSubseq(s string) int {
return process(s)
}
func process(s string) int {
sLen := len(s)
if sLen == 0 {
return 0
}
if sLen == 1 {
return 1
}
ret1 := process(s[1 : sLen-1])
ret2 := 0
ret3 := 0
if s[0] != s[sLen-1] {
ret2 = process(s[0 : sLen-1])
ret3 = process(s[1:sLen])
} else {
ret1 += 2
}
ret := getMax(ret1, ret2)
ret = getMax(ret, ret3)
return ret
}
//動(dòng)態(tài)規(guī)劃
func longestPalindromeSubseq2(s string) int {
sLen := len(s)
if sLen == 0 {
return 0
}
if sLen == 1 {
return 1
}
dp := make([][]int, sLen)
for i := 0; i < sLen; i++ {
dp[i] = make([]int, sLen)
}
for i := 0; i < sLen-1; i++ {
dp[i][i] = 1
if s[i] == s[i+1] {
dp[i][i+1] = 2
} else {
dp[i][i+1] = 1
}
}
for L := sLen - 3; L >= 0; L-- {
for R := L + 2; R < sLen; R++ {
dp[L][R] = getMax(dp[L][R-1], dp[L+1][R])
if s[L] == s[R] {
dp[L][R] = getMax(dp[L][R], 2+dp[L+1][R-1])
}
}
}
return dp[0][sLen-1]
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
執(zhí)行結(jié)果如下：
在這里插入圖片描述
