Dp 基础: 最长公共子序列
  anLrwkgbyYZS 2023年12月30日 10 0


    最长公共子序列是一个最基础的Dp,要想搞懂他可以手动模拟一下,很有效。

    下面用一个maxlen的二维数组来记录我们的比较情况, maxlen[i][j]记录的就是两个字符串 s1的前 i个字符与s2前 j 个字符的最长公共子序列

     下面介绍下最重要的两个步骤:

      if(s1[i] == s2[j])   
           maxlen[i][j] = maxlen[i-1][j-1] + 1;      

     这个步骤的意思如果字符串s1的第 i 个字符与 s2 的第 j 个字符相同,那么字符串 s1的前 i个字符与s2前 j 个字符的最长公共子序列就应该是字符串 s1的前 i-1 个字符与s2前 j -1 个字符的最长公共子序列 .
 else
    maxlen[i][j] = max(maxlen[i][j-1],maxlen[i-1][j]);

     这个步骤的意思如果字符串s1的第 i 个字符与 s2 的第 j 个字符不相同,那么字符串 s1的前 i个字符与s2前 j 个字符的最长公共子序列就应该是字符串s1的前 i-1 个字符与s2前 j 个字符的最长公共子序列  和  字符串s1的前 i个字符与s2前 j -1 个字符的最长公共子序列的最大值。

参考代码:

#include<stdio.h>
#include<string.h>
using namespace std;
const int N = 1000;
char s1[N],  s2[N]; //两个字符串
int maxlen[N][N];
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    scanf("%s %s",s1+1,s2+1); // 输入字符串,下标从 1 开始
    int i, j, len1, len2;

    len1 = strlen(s1+1); // s1 的长度
    len2 = strlen(s2+1);// s2 的长度

    memset(maxlen,0,sizeof(maxlen));

    for(i=1; i<=len1; i++)
        for(j=1; j<=len2; j++)
        {
            if(s1[i] == s2[j])
                maxlen[i][j] = maxlen[i-1][j-1] + 1;
            else
                maxlen[i][j] = max(maxlen[i][j-1],maxlen[i-1][j]);
        }
    printf("%d\n",maxlen[len1][len2]);
    return 0;
}

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年12月30日 0

暂无评论

anLrwkgbyYZS