求最长公共子序列的长度



/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
char* LCS(char* s1, char* s2 ) {
    // write code here
    int len1=strlen(s1);
    int len2=strlen(s2);
    int max=0;
    //设置二维数组dp保存最长公共子序列长度,
    int dp[2000][2000]={0};
    for(int i=0;i<len1;i++)
    {
        for(int j=0;j<len2;j++)
        {
            //s1第i个字符和s2第j个字符相等,dp[i][j]根据dp[i][j]进行累加
            if(s1[i] == s2[j])
            {

                dp[i+1][j+1]=dp[i][j]+1;
                //max记录最长公共子序列的长度
                if(dp[i+1][j+1]>max)
                    max=dp[i+1][j+1];
            }
            //s1第i个字符和s2第j个字符不相等,根据状态转移方程
            else
            {
                dp[i+1][j+1]=(dp[i+1][j]>dp[i][j+1]?dp[i+1][j]:dp[i][j+1]);
            }
        }
    }
    printf("%d",max);
    return NULL;
}



全部评论
感谢大佬的分享,很厉害
点赞 回复 分享
发布于 2022-10-23 19:01 陕西

相关推荐

待现的未见之事:起码第一句要把自己的优势说出来吧。比如什么xx本27届学生,随时到岗....
点赞 评论 收藏
分享
昨天 23:26
河南大学 Java
双非本,刚学完Redis,项目只有外卖和点评,八股没准备,算法只有lqb省一,感觉敲的项目也是一言难尽没怎么吸收。怎么你们都有实习了
大牛之途:27急个锤子,你投日常实习最好的时间就是9,10月份,那时候暑期实习都结束了,正是缺人的时候。这份日常又能给你的暑期实习增加竞争力,暑期找的好了秋招也不怕了,都是环环相扣的
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客企业服务