#77 Longest Common Subsequence-程序员宅基地

技术标签: lintcode  dynamic programming  

题目描述:

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Clarification
Example

For "ABCD" and "EDCA", the LCS is "A" (or "D""C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

题目思路:

这题还是用dp解。用dp[i][j]表示A[0...i-1], B[0...j-1]的LCS长度。那么我们就可以得到dp方程:

1). 如果A[i - 1] == B[i - 1], 那么我们有3种选择:把这两个char算进去,于是长度有dp[i - 1][j - 1] + 1, 不把这两个char算进去,于是长度可以为dp[i - 1][j], dp[i][j - 1],这3中里面取最大值;

2). 如果item 1)不成立,那么我们在这3中选择里取最大:dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] 

Mycode (AC = 15ms):

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string A, string B) {
        // write your code here
        if (A.size() == 0 || B.size() == 0) {
            return 0;
        }
        
        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
        
        // dp[i][j] denote length of LCS for A[0...i - 1] and B[0...j - 1]
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = max(dp[i][j - 1], max(dp[i - 1][j - 1] + 1, dp[i - 1][j]));
                }
                else {
                    dp[i][j] = max(dp[i][j - 1], max(dp[i - 1][j - 1], dp[i - 1][j]));
                }
            }
        }
        
        
        return dp[A.size()][B.size()];
    }
};


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/haifischxia/article/details/52335179

智能推荐

Codeforces 734C. Anton and Making Potions_codeforces time assassin-程序员宅基地

文章浏览阅读329次。C. Anton and Making Potions time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard output Anton is playing a very interesting computer game, but now he_codeforces time assassin

redhat下yum命令安装(替换为centos yum命令)_redhat yum安装yum-4.2.17-6.el8.noarch-程序员宅基地

文章浏览阅读507次。redhat下yum命令安装(替换为centos yum命令)redhat默认自带的yum源需要注册,才能更新,报错:This system is not registered to Red Hat Subscription Management. You can use subscription-manager to register.可替换为centos对应的源。 操作如下:1.检查是..._redhat yum安装yum-4.2.17-6.el8.noarch

JavaWeb中请求转发和重定向的区别一篇就够了_java web重定向和请求转发区别-程序员宅基地

文章浏览阅读711次,点赞3次,收藏6次。标题_java web重定向和请求转发区别

ggplot2绘图点的形状不够用怎么办?-程序员宅基地

文章浏览阅读3.1k次。群里有这么一个问题:请问老师,fviz_pca_ind 做pca,当设置geom.ind = “point”,group>6时,就不能显示第7,8组的点,应该如何处理(在不设置为文本..._r语言出图点不够用

[笔记]Git入门安装---svn安装-svn基础知识简单介绍---提交项目到码云-idea下down出码云项目-最后到idea工具集成git和svm简单操作步骤的简单讲解。--【实用篇】_svm怎么提交项目-程序员宅基地

文章浏览阅读415次。文章目录前言一、起步安装git二、Svn安装1.引入库2.读入数据总结前言 今天老师讲了svn和git一些语句,还有一些简单的操作步骤,记录下来老惯例加深一下自己的印象。 哎呀呀,不知不觉已经习惯了在博客中享受孤独,这也映衬了自己非常羡慕的一位程序员说过的话:最高级的自律是享受孤独。 _svm怎么提交项目

HTML5笔记_mashiro_option.site_url-程序员宅基地

文章浏览阅读193次。HTML51.First Html file<!-- 向浏览器声明文件类型,默认Html --><!DOCTYPE html><!----><html lang="en"><!-- 网页头 --><head> <!-- meta描述性标签,一般用于SEO --> <meta charset="UTF-8"> <meta name="keywords" content="htmlStu_mashiro_option.site_url

随便推点

Mysql 事务 锁表 锁行-程序员宅基地

文章浏览阅读708次。Mysql 事务 锁表 锁行1、事务隔离级别为读提交时,写数据只会锁住相应的行2、事务隔离级别为可重复读时(Mysql 默认),如果检索条件有索引(包括主键索引)的时候,默认加锁方式是next-key 锁;如果检索条件没有索引,更新数据时会锁住整张表。一个间隙被事务加了锁,其他事务是...

使用GPG加密通讯,设置git提交验证密钥_end pgp message-程序员宅基地

文章浏览阅读880次。使用命令行创建 GPG 密钥使用以下 shell 命令:gpg2 --full-gen-key此命令生成由公钥和私钥组成的密钥对。其他人使用您的公钥来验证和/或解密您的通信。分发您的公共密钥尽可能广泛地,尤其是你知道将要收到你正宗的通信,如邮件列表谁的人。例如,Fedora 文档项目要求参与者在他们的自我介绍中包含一个 GPG 公钥。一系列提示将指导您完成整个过程。如果需要,按Enter键分配默认值。第一个提示要求您选择您喜欢的键类型:请选择您想要的密钥类型: (1) RSA 和 RSA(_end pgp message

elasticsearch mapping 学习(parent-child)_es 父子文档mapping-程序员宅基地

文章浏览阅读1.5k次。ES 父子文档查询父子文档的特点1. 父/子文档是完全独立的。2. 父文档更新不会影响子文档。3. 子文档更新不会影响父文档或者其它子文档。父子文档的映射与索引1. 父子关系 type 的建立必须在索引新建或 update-mapping 时候确定好PUT /company{ "mappings": { "b_es 父子文档mapping

前端工程师如何提升能力 提高效率有哪些方法_如何提高自己的前端技术能力-程序员宅基地

文章浏览阅读2.3k次。  前端工程师如何提升能力?提高效率有哪些方法?Web前端工程师的工作内容杂且多,除了要负责切图、写HTML/CSS/JS外,还要解决一系列的浏览器兼容性、网页性能优化等问题,所以提高前端工程师的开发效率势在必行。下面就给大家分享提高效率的几个方法助力你成为高产、高效的Web前端开发工程师。​  1、使用正确的工具。正所谓“工欲善其事必先利其器”,如果你是一个网页设计师,你可能需要Photoshop和Illustrator。如果你是一名开发人员,你需要一些优秀的Web开发应用程序。拥有一些优秀的、你_如何提高自己的前端技术能力

C# Random的种子-程序员宅基地

文章浏览阅读4.7k次。问题是这样的 。遍历界面上所有的TextBox

centos7安装弱口令破解工具hydra_centos hydra下载-程序员宅基地

文章浏览阅读740次。1、下载压缩包wget https://github.com/vanhauser-thc/thc-hydra/archive/master.zip2、安装gcc和解压命令yum -y install gcc libssh-devel openssl-develyum install -y unzip zip3、解压,进入解压目录unzip master.zipcd thc-hydra-master/4、编译运行./configuremake &&make install_centos hydra下载

推荐文章

热门文章

相关标签