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

问题描述

给定两个序列,求出它们的最长公共子序列。 如:序列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 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之旋转数组的最小数字(九度OJ1386)

题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1...

18110
来自专栏算法修养

POJ 3233 Matrix Power Series(矩阵快速幂)

Matrix Power Series Time Limit: 3000MS Memory Limit: 131072K Total Subm...

3265
来自专栏武培轩的专栏

剑指Offer-调整数组顺序使奇数位于偶数前面

题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶...

3426
来自专栏算法修养

POJ-2346 Lucky tickets(线性DP)

Lucky tickets Time Limit: 1000MS Memory Limit: 65536K Total Submissions...

2297
来自专栏kevindroid

leetcode110 Balanced Binary Tree

1275
来自专栏ml

poj-------Common Subsequence(poj 1458)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submiss...

2645
来自专栏Golang语言社区

Go语言单链表实现方法

本文实例讲述了Go语言单链表实现方法。分享给大家供大家参考。具体如下: 1. singlechain.go代码如下: ////////// //单链表 -- 线...

3308
来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

3436
来自专栏LeetCode

LeetCode 169. Majority Element

思路:数组中有一个数字的出现次数超过一半,也就是说这个数字的出现次数比其他的所有的数字的出现次数之和还要多。因此我们可以考虑遍历数组的时候保存两个值,一个是数组...

291
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之旋转数组的最小数字(九度OJ1386)

题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1...

18410

扫码关注云+社区