专栏首页ACM算法日常DP专题 3 | LCS最长公共子序列 - POJ 1458

DP专题 3 | LCS最长公共子序列 - POJ 1458

DP题目太多,加快上题速度~~

Common Subsequence(公共子序列问题)

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

简单说就是Z是X的子序列。给定序列X和Y,求出最长公共子序列的长度。

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

每行是两个字符串序列。

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

输出最长公共子序列的长度。

Sample Input

abcfbc         abfcab 
programming    contest 
abcd           mnp

Sample Output

4 
2
0

LCS算法是一个二维DP,核心思想是:

dp[i][j]表示数列A[1~i]和数列B[1~j]的最长子序列长度。

当A[i]等于A[j]时,dp[i][j] = dp[i-1][j-1]+1,表示增加了一个元素。

如果A[i]和A[j]不相等,则不增加元素,但是要记录dp值,因为后续需要依赖该值,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

实现采用记忆化递归的方式非常自然简单,缺点是性能差,虽然LCS可以采用递推的方式做,而且从dp[0][0]开始递推也比较容易实现,但是注意dp[i][0]都为0,dp[0][j]都为0,采用二维循环,对于数列a和b,每次遍历b都是固定a的一个值,其实是计算表中的一行。理解起来比递归要复杂些,仔细揣摩一下吧!

下图可以帮助理解一下~

源代码:记忆化递归

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

int d[1000][1000];
string s1, s2;

int dp(int i, int j)
{
    if(d[i][j] != -1)
        return d[i][j];

    if(i==0 || j==0)
        return 0;

    if(s1[i-1] == s2[j-1])
        d[i][j] = dp(i-1, j-1) + 1;
    else
        d[i][j] = std::max(dp(i-1, j), dp(i, j-1));

    return d[i][j];
}

int main()
{
    while(cin>>s1>>s2)
    {
        memset(d, -1, sizeof(d));
        cout << dp(s1.length(), s2.length()) <<endl;
    }

    return 0;
}

源代码:递推 0ms

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

char s1[1000];
char s2[1000];
int dp[1000][1000];

int main() {
    while (cin >> s1 >> s2) {
        int l1 = strlen(s1);
        int l2 = strlen(s2);
        int i, j;

        for (i = 0; i <= l1; i++)
            dp[i][0] = 0;

        for (j = 0; j <= l2; j++)
            dp[0][j] = 0;

        for (i = 1; i <= l1; i++) {
            for (j = 1; j <= l2; j++) {
                if (s1[i - 1] == s2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        cout << dp[l1][l2] << endl;
    }
    return 0;
}

下集预告:0-1背包系统

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-12

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • DP专题 | 数字三角形 - POJ 1163

    从本篇开始,准备做一系列的专题讲解,主要参考《算法竞赛入门经典》、《算法竞赛进阶指南》两本书。主要是为了能够更加系统的讲解各个知识点,这两本书已经讲得很好了,建...

    ACM算法日常
  • 最长上升子序列(LIS)算法

    LIS(Longest Increasing Subsequence)最长上升子序列 一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列...

    ACM算法日常
  • 新手ACM算法学习建议

    一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功。ACM主要是考算法的,主要时间是花在思考算法上,不是花在写程序与debug上。

    ACM算法日常
  • HUST 1602 - Substring

    题目描述 This problem is quiet easy. Initially, there is a string A. Then we do ...

    ShenduCC
  • 动态 | DeepMind 首次披露旗下专利申请情况

    近日,DeepMind首次披露了一系列国际专利,这些专利涉及了现代机器学习的一些基础方面,对在人工智能领域进行商业化的任何人都有着潜在的意义。

    AI科技评论
  • 项目经验不重样!3个基于 SpringBoot 的图片识别处理系统送给你!

    最近看了太多读者小伙伴的简历,发现各种商城/秒杀系统/在线教育系统真的是挺多的。推荐一下昨晚找的几个还不错的基于 Java 的图片识别处理系统。

    Guide哥
  • 工欲善其事,必先利其器

    随着嵌入式开发技术的进步,产品功能的越来越复杂,传统全靠工程师手动编码测试,验证的开发模式俨然已经无法满足开发中大型工程的需求,急需改变传统模式寻求新的模式和方...

    用户1605515
  • Sequelize 傻瓜式操作

    模型的all方法,返回表中的所有数据 User .findOne({//还有find、findAll等方法 where: ...

    flytam
  • 一湖数据,几度春秋

    2017年底的一场reorg,让微软的Azure Data Lake(数据湖)队伍拆的七零八落,Raghu Ramakrishnan也黯然神伤,被reorg成了...

    用户1564362
  • netty源码分析二之EventLoopGroup初始化

    这里的DEFAULTEVENTLOOP_THREADS的默认值是cpu核数乘以2:

    开发架构二三事

扫码关注云+社区

领取腾讯云代金券