首页 > 代码库 > NYOJ -37回文字符串
NYOJ -37回文字符串
这道题看了好大会没有思路，上网一搜发现这么简单，但是我为什么就想不到呢，？？就是求和它的逆序之后的字符串最长公共子序列，然后用总的长度减去它就行了。原因是是因为只要是在公共子序列里面，那么他就是对称的，少的那些就是需要补的
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int N = 1002; 8 int dp[N][N]; 9 int main()10 {11 int n;12 scanf("%d", &n);13 while (n--)14 {15 memset(dp, 0, sizeof(dp));16 string s1, s2;17 cin >> s1;18 int len = s1.length();19 for (int i = 0; i < len; i++)20 s2[i] = s1[len - i - 1];21 //求最长公共子序列22 for (int i = 1;i <= len; i++)23 {24 for (int j = 1; j <= len; j++)25 {26 if (s1[i - 1] == s2[j - 1])27 dp[i][j] = dp[i - 1][j - 1] + 1;28 else29 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);30 }31 }32 printf("%d\n", len - dp[len][len]);33 }34 35 return 0;36 }
NYOJ -37回文字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。