给定一个字符串,找到其中最长的回文子序列,并返回该序列的长度。
注:回文序列是指这个序列无论从左读还是从右读都是一样的。
本题中子序列字符串任意位置删除k(len(s)>=k>=0)个字符后留下的子串。
数据范围:字符串长度满足
进阶:空间复杂度 , 时间复杂度
输入一个字符串
输出最长回文子序列
abccsb
4
分别选取第2、3、4、6位上的字符组成“bccb”子序列是最优解
abcdewa
3
分别选取第一个和最后一个a,再取中间任意一个字符就是最优解
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; // 时间复杂度O(N^2),空间复杂度O(N^2) vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0)); for (int i = 0; i < s.size(); ++i) dp[i][i] = 1; for (int i = s.size() - 1; i >= 0; --i) { for (int j = i + 1; j < s.size(); ++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]); } } cout << dp[0][s.size() - 1]; return 0; }
#include <iostream> #include <cstdio> #include <string> using namespace std; const int MAXN = 1000 + 10; int dp[MAXN][MAXN]; int main() { string str; cin >> str; for(int i = 0; i < str.size() - 1; ++i) { dp[i][i] = 1; } for(int i = str.size() - 1; i >= 0; --i) { for(int j = i + 1; j < str.size(); ++j) { if(str[i] == str[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } } cout << dp[0][str.size() - 1] << endl; return 0; }
public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case String a = in.next(); char[]s=a.toCharArray(); int len=s.length; int [][]dp=new int[len+1][len+1]; for(int i=1;i<=len;i++){ for(int j=len;j>0;j--){ if(s[i-1]==s[j-1]){ dp[i][len-j+1]=dp[i-1][len-j]+1; } else{ dp[i][len-j+1]=Math.max(dp[i-1][len-j+1],dp[i][len-j]); } } } System.out.println(dp[len][len]); } }
package main import ( "fmt" ) func main() { var s string fmt.Scan(&s) dp:=make([][]int,len(s)+1) for i,_:=range dp{ dp[i]=make([]int,len(s)+1) } for i:=0;i<len(s);i++{ for j:=0;j<len(s);j++{ if s[i]==s[len(s)-j-1]{ dp[i+1][j+1]=dp[i][j]+1 }else{ dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]) } } } fmt.Println(dp[len(s)][len(s)]) } func max(a,b int)int{ if a>b{ return a } return b }
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { string s; cin>>s; int n=s.size(); //最长回文子串从右下到左上 vector<vector<int> > dp(n+1,vector<int>(n+1,0)); for(int i=0;i<n;i++) { dp[i][i]=1; } for(int i=n-1;i>=0;i--) { for(int 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]); } } } cout<<dp[0][n-1]<<endl; return 0; }
import sys def longnums(a): if(len(a) != 0): nums = a[0] n = len(a[0]) dp = [[0 for col in range(len(nums))] for row in range(len(nums))] for i in range(len(nums)): dp[i][i] = 1 for L in range(2,n+1): for i in range(n-1): j = L + i - 1 if(j > n-1): break if(nums[i] == nums[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][-1] for line in sys.stdin: a = line.split() print(longnums(a))