最长公共子序列运用

于 2017-08-06 18:17:49 发布
阅读量715 收藏 2
点赞数
分类专栏： C/C++
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/helloworlddm/article/details/76785423
版权
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
思路：将原字符串反转，求出元字符串与反转字符串最长公共子序列(也就是最长的回文串);
c++代码(网上搜的)：

点击(此处)折叠或打开

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. const int MAXN=1010;
  5. int dp[MAXN][MAXN];

  7. class Solution
  8. {
  9. public:
  10.    int solve(string &s)
  11.    {
  12.        return s.length()-getLCS(s);
  13.    }

  15.    int getLCS(string &s1)
  16.    {
  17.        string s2(s1);
  18.        reverse(s2.begin(),s2.end());
  19.        int len=s1.length();
  20.        memset(dp,0,sizeof dp);
  21.        for(int i=0;i<len;++i)
  22.        {
  23.            for(int j=0;j<len;++j)
  24.            {
  25.                if(s1[i]==s2[j])
  26.                    dp[i+1][j+1]=dp[i][j]+1;
  27.                else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
  28.            }
  29.        }
  30.        return dp[len][len];
  31.    }
  32. };

  34. int main()
  35. {
  36.    string s;
  37.    while(cin>>s)
  38.    {
  39.        Solution solution;
  40.        cout<<solution.solve(s)<<endl;
  41.    }
  42.    return 0;
  43. }


c语言代码：

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. void reverse(char *str,int from,int to)
  5. {
  6.     while (from < to)
  7.     {
  8.         char temp = str[from];
  9.         str[from++] = str[to];
  10.         str[to--] = temp;
  11.     }
  12. }
  13. int getLcs(char *str1,char *str2,int length)
  14. {
  15.     //printf("%s %s\n",str1,str2);//居然是一样的
  16.     int dp[length][length];
  17.     int i =0,j = 0;
  18.     for (i = 0;i <length;i++)
  19.     {
  20.         for (j = 0;j < length;j++)
  21.             dp[i][j] = 0;
  22.     }
  23. //    int i = 0,j = 0;
  24.     for (i = 0;i < length;i++)
  25.     {
  26.         for (j = 0;j < length;j++)
  27.         {
  28.             if (i == 0 || j == 0)
  29.             {
  30.                 if (str1[i] == str2[j])
  31.                 {
  32.                     dp[i][j] = 1;
  33.                 }
  34.                 else
  35.                 {
  36.                     if (i > 0)
  37.                         dp[i][j] = dp[i-1][j];
  38.                     if (j > 0)
  39.                         dp[i][j] = dp[i][j-1];
  40.                 }
  41.             }
  42.             else if (str1[i] == str2[j])
  43.             {
  44.                 dp[i][j] = dp[i-1][j-1]+1;
  45.             }
  46.             else {
  47.                 dp[i][j] = ((dp[i-1][j] > dp[i][j-1]) ?dp[i-1][j]:dp[i][j-1]);
  48.             }
  49.         }
  50.     }
  51.     return dp[length-1][length-1];
  52. }
  53. int main()
  54. {
  55.     char str[1024];//注意下字符串指针
  56.     //char *str1 = "abcda";
  57.     //char *str2 = "adcba";
  58.     
  59.     while (gets(str))
  60.     {
  61.         int len = strlen(str);
  62.         char str1[1024];
  63.     //    char *str1 = str;
  64.     //    printf("str1 = %s\n",str1);
  65.         
  66.         strcpy(str1,str);
  67.         reverse(str,0,len-1);

  69.         
  70.         //printf("str2 = %s\n",str2);
  71.         int result = getLcs(str1,str,len);

  73.         printf("%d\n",(len-result));
  74.         //free(str2);
  75.     }
  76.     return 0;
  77.     //getLcs()
  78.     
  79. }


<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script>
阅读(687) | 评论(0) | 转发(0) |
0

上一篇：字符串反转

下一篇：[cisco]用宏定义写出swap（x，y）

相关热门文章
    给主人留下些什么吧！~~
    评论热议
    评论
    添加红包

    请填写红包祝福语或标题

    个

    红包个数最小为10个

    元

    红包金额最低5元

    当前余额3.43元 前往充值 >
    需支付：10.00元
    成就一亿技术人!
    领取后你会自动成为博主和红包主的粉丝 规则
    hope_wisdom
    发出的红包

    打赏作者

    helloworddm

    你的鼓励是我创作最大的动力

    ¥1 ¥2 ¥4 ¥6 ¥10 ¥20
    扫码支付：¥1
    获取中
    扫码支付

    您的余额不足，请更换扫码支付或充值

    打赏作者

    实付元
    使用余额支付
    点击重新获取
    扫码支付
    钱包余额 0

    抵扣说明：

    1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
    2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

    余额充值