点击上方蓝字关注力扣
下面开始今天的学习～
力扣 516.最长回文子序列（点击查看题目）
题目描述
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"输出：2解释：一个可能的最长回文子序列为 "bb" 。
提示：
  • 1<= s.length <= 1000
  • s 仅由小写英文字母组成
解决方案
方法一：动态规划
对于一个子序列而言，如果它是回文子序列，并且长度大于 22，那么将它首尾的两个字符去除之后，它仍然是个回文子序列。因此可以用动态规划的方法计算给定字符串的最长回文子序列。
用 dp[i][j] 表示字符串 s 的下标范围 [i,j] 内的最长回文子序列的长度。假设字符串 s 的长度为 n，则只有当 0≤i≤j<n 时，才会有 dp[i][j]>0，否则 dp[i][j]=0。
由于任何长度为 1 的子序列都是回文子序列，因此动态规划的边界情况是，对任意 0≤i<n，都有 dp[i][i]=1。
当 i < j 时，计算 dp[i][j] 需要分别考虑 s[i] 和 s[j] 相等和不相等的情况：
  • 如果 s[i] = s[j]，则首先得到 s 的下标范围 [i+1, j-1] 内的最长回文子序列，然后在该子序列的首尾分别添加 s[i] 和 s[j]，即可得到 s 的下标范围 [i,j] 内的最长回文子序列，因此 dp[i][j]=dp[i+1][j−1]+2；
  • 如果 s[i] ≠ s[j]，则 s[i] 和 s[j] 不可能同时作为同一个回文子序列的首尾，因此 dp[i][j]=max(dp[i+1][j],dp[i][j−1])。
由于状态转移方程都是从长度较短的子序列向长度较长的子序列转移，因此需要注意动态规划的循环顺序。
最终得到 dp[0][n−1] 即为字符串 s 的最长回文子序列的长度。
Java

classSolution {publicintlongestPalindromeSubseq(String s) {int n = s.length();int[][] dp = newint[n][n];for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1;char c1 = s.charAt(i);for (int j = i + 1; j < n; j++) {char c2 = s.charAt(j);if (c1 == c2) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } }return dp[0][n - 1]; }}
C#
publicclassSolution {publicintLongestPalindromeSubseq(string s) {int n = s.Length;int[,] dp = newint[n, n];for (int i = n - 1; i >= 0; i--) { dp[i, i] = 1;char c1 = s[i];for (int j = i + 1; j < n; j++) {char c2 = s[j];if (c1 == c2) { dp[i, j] = dp[i + 1, j - 1] + 2; } else { dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]); } } }return dp[0, n - 1]; }}
JavaScript
var longestPalindromeSubseq = function(s) {const n = s.length;const dp = newArray(n).fill(0).map(() =>newArray(n).fill(0));for (let i = n - 1; i >= 0; i--) { dp[i][i] = 1;const c1 = s[i];for (let j = i + 1; j < n; j++) {const c2 = s[j];if (c1 === c2) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } }return dp[0][n - 1];};
Python3
classSolution:deflongestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0] * n for_in range(n)]for i in range(n - 1, -1, -1): dp[i][i] = 1for j in range(i + 1, n):if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])return dp[0][n - 1]
Golang  
funclongestPalindromeSubseq(s string)int { n := len(s) dp := make([][]int, n)for i := range dp { dp[i] = make([]int, n) }for i := n - 1; i >= 0; i-- { dp[i][i] = 1for 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]}funcmax(a, b int)int {if a > b {return a }return b}
C++
classSolution {public:intlongestPalindromeSubseq(string s){int n = s.length();vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1;char c1 = s[i];for (int j = i + 1; j < n; j++) {char c2 = s[j];if (c1 == c2) { 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]; }};
C
intlongestPalindromeSubseq(char* s){int n = strlen(s);int dp[n][n];memset(dp, 0, sizeof(dp));for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1;char c1 = s[i];for (int j = i + 1; j < n; j++) {char c2 = s[j];if (c1 == c2) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = fmax(dp[i + 1][j], dp[i][j - 1]); } } }return dp[0][n - 1];}
复杂度分析
  • 时间复杂度：O(n∧2)，其中 nn 是字符串 ss 的长度。动态规划需要计算的状态数是 O(n∧2)
  • 空间复杂度：O(n∧2)，其中 nn 是字符串 ss 的长度。需要创建二维数组 dp，空间是 O(n∧2)。
BY / 
本文作者：力扣
编辑&版式：霍霍
声明：本文归“力扣”版权所有，如需转载请联系。
点个在看，少个 bug👇
继续阅读
阅读原文
关键词
字符
子序列
字符串
长度
回文子序列