LeetCode 516. 最长回文子序列
题目描述
思路分析
这是一个典型的区间动态规划问题，我们要在字符串中找到最长的回文子序列的长度。
我们定义状态：
dp[i][j]表示s[i...j]（包含 i 和 j）这个区间内的最长回文子序列的长度目标是求：
dp[0][n-1]
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func longestPalindromeSubseq(s string) int {
n := len(s)
// 定义 dp[i][j] 表示从 i 到 j 的最长回文子序列长度
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
dp[i][i] = 1 // 单个字符是回文
}
// 从下往上遍历，保证 i < j 的状态都被计算
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][n-1]
}
- 时间复杂度：O(n²)，共需填充 n × n 个状态。
- 空间复杂度：O(n²)，使用了二维 dp 数组。
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！