动态规划法(三)——最长公共子序列

问题描述

给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子序列为{b,c,b,a}

  • 子序列:子序列为原序列的一个子集,并不要求连续,但要求子序列中元素的顺序和原序列元素的顺序一致。

定理

设两个序列分别是X={x1,x2……,xm},Y={y1,y2……,yn},它们的最长公共子序列为Z={z1,z2,……,zk}。

  1. 若xm=yn,则先求Xm-1和Yn-1的最长公共子序列,再在其尾部加上xm即可得Xm和Yn的最长公共子序列。
  2. 若xm!=yn,则必须分别求Xm、Yn-1和Xm-1、Yn的最长公共子序列,其中较长者就是Xm和Yn的最长公共子序列。

数据结构

  • c[i][j]: 用来记录Xi和Yj的最长公共子序列的长度。
  • s[i][j]: 用来标识Xi和Yi的最长公共子序列是由哪种情况得来:c[i][j-1]、c[i-1][j]、c[i][j]+1。 该数组能还原出最长公共子序列。

算法思路

1. 生成c数组和s数组所有元素

  1. 将c数组的第0行、第0列初始化为0;
  2. 从c数组的第一行、第一列开始,依次从左向右、从上到下填充元素值: a)若x[i]==y[j],则c[i][j]=c[i-1][j-1]+1,s[i][j]=1; b)若x[i]!=y[j],则分别计算c[i][j-1]、c[i-1][j],将大的那个作为c[i][j];并且,如果c[i-1][j]>=c[i][j-1],则s[i][j]=2;如果c[i-1][j]< c[i][j-1],则s[i][j]=3;

2. 根据s数组求得最长公共子序列

代码实现

private int[][] c;
private int[][] s;

1. 生成c数组和s数组所有元素

void LCSLength(String a, String b){
    // x和y的最前端分别加上0
    char[] x = ("0"+a).toCharArray();
    char[] y = ("0"+b).toCharArray();

    c = new int[x.length][y.length];
    s = new int[x.length][y.length];

    // 初始化c、s
    for( int i=0; i<x.length; i++ ){
        c[i][0] = 0;
    }
    for( int i=0; i<y.length; i++ ){
        c[0][i] = 0;
    }

    // 从上到下、从左到右填充c、s数组
    for( int i=1; i<x.length; i++ ){
        for( int j=1; j<y.length; j++ ){
            if( x[i]==y[j] ){
                c[i][j] = c[i-1][j-1]+1;
                s[i][j] = 1;
            }
            else if ( c[i-1][j] >= c[i][j-1] ){
                c[i][j] = c[i-1][j];
                s[i][j] = 2;
            }
            else {
                c[i][j] = c[i][j-1];
                s[i][j] = 3;
            }
        }
    }
}

2. 根据s数组求得最长公共子序列

StringBuilder sb = new StringBuilder();

void CLCS( int i, int j ){
    if ( i==0 || j==0 ) return;
    if ( s[i][j]==1 ) {
        CLCS( i-1,j-1 );
        sb.append( x[i] ); // 为了让公共子序列正序输出,因此需要在递归调用之后将x[i]添加至sb
    }
    else if ( s[i][j]==2 ){
        CLCS( i-1,j );
    }
    else {
        CLCS( i,j-1 );
    }
}

图示

  • 初始化c和s数组,将第0行、第0列都设为0:
  • 从第一行、第一列开始,依次从左到右、从上到下填充c和s数组:
  • 当c和s都填充完毕后,就可以根据s数组找到最长公共子序列 从s数组最右下角的元素开始: a)若s[i][j]==1,则找到一个字符,并继续比较左上角的元素; b)若s[i][j]==2,则继续比较上方的元素; c)s[i][j]==3,则继续比较左侧的元素。 d)直到i==0或j==0为止。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五毛程序员

Cocos2d-x基础篇C++

2593
来自专栏深度学习之tensorflow实战篇

python高阶函数:map(f,[list]),reduce(f,[list],可选初始值),

map,reduce和filter三个函数在python3和python2中发生了较大的差异。具体请看文章后面部分。 1. python的map()函数 ...

3074
来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

901
来自专栏Jack-Cui

Day3、Python

题目 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1、程序分析     根据题意可知,需要用到字符串的操作方法。本题中要用到的三...

1750
来自专栏PHP在线

php面试题(二)

1 <?php echo count (false); $a = count ("567") + count(null) + count(false); ec...

3438
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

2727
来自专栏数据结构与算法

洛谷P2181 对角线(组合数)

题目描述 对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: ? 输入输出格式 输入格式: 第一行一个...

3245
来自专栏软件开发 -- 分享 互助 成长

使用数字进行字符遍历

有些时候使用数字进行遍历,然后将数字转化成需要的进制数,再将进制数对应成需要的字符是一种非常有效的方法。 如: 输入一个正整数X,在下面的等式左边的数字之间添加...

19110
来自专栏python3

python random模块

随机输出一个0~4的数字和range()输出的数字,去比较。猜对了,就是字母,否则是数字

652
来自专栏ACM算法日常

HDU1106:排序 (重新修正)

之前发过一篇HDU 1106的题目,但是因为有童鞋说那篇的源码提交后超时,我们的AlphaWA童鞋重新做了一遍,这次是0ms!算是修正之前的问题,非常感谢~

731

扫码关注云+社区