最长公共子序列（动态规划）_键盘上的精灵的博客-程序员秘密

定义：一个数列，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。

考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：

（1）如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；

（2）如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；

（3）如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。

这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。

DP最终处理的还是数值（极值做最优解），找到了最优值，就找到了最优方案；为了找到最长的LCS，我们定义dp[i][j]记录序列LCS的长度，合法状态的初始值为当序列X的长度为0或Y的长度为0，公共子序列LCS长度为0，即dp[i][j]=0，所以用i和j分别表示序列X的长度和序列Y的长度，状态转移方程为
dp[i][j] = 0 如果i=0或j=0
dp[i][j] = dp[i-1][j-1] + 1 如果X[i-1] = Y[i-1]
dp[i][j] = max{ dp[i-1][j], dp[i][j-1] } 如果X[i-1] != Y[i-1]

注意：输入字符串时，不要用cin或scanf输入，可能字符串中包含空格不能完全接收数据。因此用gets,getchar,getline或者fgets。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
int dp[1005][1005];
int main()
{
    char a[1005],b[1005];
    int i,j,len1,len2;
    while(gets(a))
    {
        gets(b);
        len1=strlen(a);
        len2=strlen(b);
        memset(dp,0,sizeof(dp));
        for(i=1; i<=len1; i++)
            for(j=1; j<=len2; j++)
            {
                if(a[i-1]==b[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        cout<<dp[len1][len2]<<endl;
    }
}

本文链接：https://blog.csdn.net/yangkunpengD/article/details/51275502

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

风控建模很难？一篇文章教你从0到1建立回归模型_数据分析v的博客-程序员秘密

本文导航⊙1. 回归模型：一场盛大的变量选秀⊙ 2. 海选-精选-群组PK-联排⊙ 3. 衡量模型效果的重要指标⊙ 4. 总结与后续预告在当今互联网经济...

curl txt批量_怎样批量下载百度云盘文件 php远程curl批量下载百度云盘_weixin_39812465的博客-程序员秘密

[php]代码库

【收藏】Appium 国内下载地址（百度云盘，已更新至 1.3.4.1）_沈伟-测试前行者的博客-程序员秘密

链接是Appium相关安装包下载地址（exe&dmg格式），如需自取：）最新更新的是： appium-1.3.4.dmg& AppiumForWindows-1.3.4.1.zip现已更新到 TesterHome官方百度网盘下载地址： http://pan.baidu.com/s/1jGvAISuAppium各版本release doc地址： https:

编译原理-第二篇_编译原理闭包_蓝猫_虹的博客-程序员秘密

2.词法分析词法分析的目的是什么呢？是把一长串的字符分解成一个个的词素，并且生成（id，2）这种作为语法分析的基础。首先是词法单元，词素等的定义。然后是如何输入。三是输入后如何识别。识别后如何组成中间式子。 1.三个关键词词法单元，词素，模式词法单元：词法单元由一个词法单元名和一个可选的属性值组成。词法单元名是一个表示某种词法单位的抽象符号。比如一个特定...

明人不说暗话，当IT公司老板落水，各部门怎样抢救_领导暗话_想学习大数据的博客-程序员秘密

　　公司高层　　　　公司副总A：咱们开个会研究一下这个事情怎么处理。　　公司副总B：如果老板没有救成功，下任是谁呢？会不会影响公司的上市？　　公司副总C：我认为咱们开会应该讨论两个方案，一个是救人方案，一个是危机公关方案。　　公司副总D：嘘！专心工作，老板是游泳高手。　　公司副总E：为了防止万一，我还是吩咐各部门准备营救方案吧。　　小秘书：（边记录边想）老板的下一任是谁呢，是不是比...

Servlet详解——生命周期、ServletConfig和ServletContext区别_Tao_Yuanqiang的博客-程序员秘密

一、servlet的生命周期二、ServletConfig和ServletContext的区别1.servletConfig123获取ServletConfig对象方式：//1.获取ServletConfig对象ServletConfig sc = this.getServletConfig();<1、读取参数信息：此为xml方式<servlet> <servlet-name>test3</servlet-name> <s