2021-02-08:给定一个字符串str,请问这个字符串的最长回文子序列长度是多少?
【摘要】 2021-02-08:给定一个字符串str,请问这个字符串的最长回文子序列长度是多少?福哥答案2021-02-08:自然智慧即可。1.原序列和反序列求公共子序列。无代码。2.递归。有代码。3.动态规划。有代码。根据动态规划表,dp[i][j]取【左边】,【下边】,【左下边】或者【左下边+2】)的最大值。【左下边】还是【左下边+2】?i==j,取【左下边+2】;i!=j,取【左下边】。代码用g...
2021-02-08:给定一个字符串str,请问这个字符串的最长回文子序列长度是多少?
福哥答案2021-02-08:
自然智慧即可。
1.原序列和反序列求公共子序列。无代码。
2.递归。有代码。
3.动态规划。有代码。
根据动态规划表,dp[i][j]取【左边】,【下边】,【左下边】或者【左下边+2】)的最大值。
【左下边】还是【左下边+2】?i==j,取【左下边+2】;i!=j,取【左下边】。
代码用golang编写,代码如下:
```go
package main
import "fmt"
func main() {
ret := longestPalindromeSubseq("bbbabbbb")
fmt.Println("递归:", ret)
ret = longestPalindromeSubseq2("bbbabbbb")
fmt.Println("动态规划:", 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
}
//动态规划
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
}
}
```
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class20/Code01_PalindromeSubsequence.java)
[力扣516](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)
[评论](https://user.qzone.qq.com/3182319461/blog/1612741776)
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
- 2025-07-28:最长特殊路径。用go语言,你有一棵无向树,节点编号从0到n-1,根节点是0。树的结构由一个长度为n-1的二
- 2025-07-27:将数组变相同的最小代价。用go语言,你有两个长度均为 n 的整型数组 arr 和 brr,还有一个整数 k
- 2025-07-26:循环数组中相邻元素的最大差值。用go语言,给定一个循环数组 nums,请找出任意两个相邻元素之间绝对差的最
- 2025-07-24:图的最大边权的最小值。用go语言,你有一个包含 n 个节点(编号 0 到 n-1)的有向带权图,图中边的信
- 2025-07-23:机器人可以获得的最大金币数。用go语言,你有一个大小为 m 行 n 列的网格。机器人从左上角位置(0,0)
评论(0)