一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 412|回复: 2
收起左侧

[动态规划] 【刷题笔记】Leetcode #1143. Longest Common Subsequence

[复制链接] |只看干货 |动态规划, 刷题
我的人缘0

升级   23%


分享帖子到朋友圈
liuzz10 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (27)
 
 
0% (0)    👎
本帖最后由 liuzz10 于 2020-8-10 08:27 编辑

【题目】Given two strings text1 and text2, return the length of their longest common subsequence.

【思路1:brute force】
穷举text 1 的所有subsequence,检查是否存在于text 2.
T(n)=O(2^n) (因为有2^n个subsequence,n为较长序列的长度)

【思路2:DP】
1. 每次看过答案后,我都先去想,这个解法是怎么想到的?之所以想到DP,是因为这个问题满足两个DP的特征:

1) DP特征1:Optimal structure
什么是Optimal structure?就是这一句话:一个问题的最优解,包含其子问题的最优解。
在这道题里,也可以说是,一个问题的Longest Common Subsequence(以下称为LCS),包含其子问题的LCS。
这道题的Optimal structure就是,两个序列的LCS包含两个序列前缀的LCS。所以子问题是两个序列前缀的LCS。这个子问题并不是一眼能看出来,而且需要分类讨论,所以我直接把子问题写给大家。
为求清晰,在解释子问题之前,我们先定义下原问题。假设X、Y为两个序列,m和n为各自的长度,原问题是求解X(length=m)=<X1, X2, …, Xm-1, Xm> 和 Y(length=n)=<Y1, Y2, …, Yn-1, Yn>这两个序列的LCS。
接下来是关于LCS的两条性质,证明省略,稍微想想就能明白。
LCS性质1:如果Xm = Ym, 那么X与Y的LCS就等于,X前缀与Y前缀的LCS加上最后一个字母,也就是说只要找到X(length=m-1)与Y(length=n-1)的LCS,就可以得到X与Y的LCS,通过加上Xm/Ym。
LCS性质2:如果Xm != Ym, 那么X与Y的LCS就等于,X(length=m-1)与Y的LCS,或者X与Y(length=n-1)的LCS,二者选其一。选哪个呢?选较长的那个LCS。
这两条性质是互斥的,是1就不会是2,是2就不会是1。这两个性质虽然很长,但讲的是一回事,都说的是要求出X与Y的LCS,需要求出X(length=m-1)和Y(length=n-1)相关的LCS。因此,这个问题符合DP特征1:Optimal structure。

2) DP特征2:Overlapping subproblem
运用DP还有一个特征,那就是子问题之间是有overlap的。正因为有overlap的问题,DP才能发挥作用,因为我们不需要重复计算同一个值,而是通过memoization将结果暂时储存在表格中,之后需要的话可以直接使用,这个操作是节省时间的关键。
这道题的子问题间有overlap,为什么呢?见下图(图片来自于网络见水印)。图中画红圈的两个子问题是一样的,所以子问题间是有重叠的。符合DP特征2:Overlapping subproblem。



2. 因此,我们猜测这个问题用DP可以解答。分析到这里思路基本上就很清楚了。
Optimal structure分析可以让我们轻松得到递归公式:


Overlapping subproblem分析可以让我们画出一个表格来存储答案。其中,表格有两个dimension,横轴是string X,纵轴是string Y,每个节点为一个字母。为什么是这样的呢?因为在第1)点里已经分析出子问题与前缀有关,因此需要把每个字母作为节点。这个表格的大小为m*n,横轴长度为m,代表X的m个子前缀序列。纵轴长度为m,代表Y的n个子前缀序列。因此,表格涵盖了X每一个长度的前缀与Y每一个长度的前缀之间的对比。


每个格子中的数字代表什么含义呢?代表LCS的长度。例如红色方框里的2代表,对比X(length=3)=<A, B, C>和Y(length=3)=<B, D, C>这两个序列,LCS的长度为2。这个2是怎么得到的呢?是通过左上角的圆框内的1加上1得到的。为什么?因为圆框内1代表X(length=2)=<A, B>和Y(length=2)=<B, D>两个序列的LCS,由于X(length=3)和Y(length=3)的第三位字母是一样的C,所以根据LCS的性质1,在前缀的LCS基础上+1就可以了。
这个表格一开始是空的,只有第一行和第一列的0,需要通过运算填满。运算的顺序有几种,其中row-major order最为常用:从左到右计算第一行,然后计算第二行,以此类推。
计算的方式就是利用递归公式里的关系。首先判断某个格子所对应的X、Y字母是否相等(也就是两个序列末位是否相等)。1)如果相等,则调取左上角最近的格子中的数字,在其基础上加上1,填入这个格子(对应LCS性质1);2)如果不相等,则调取这个格子正上方最近格子里的数字,同时还要调取这个格子左边最近格子里的数字,将两个数字进行比较,选择大数,填入这个格子(对应LCS性质2)。

3. 简化的步骤如下:
【Step 1. 计算LCS长度】
可以采用bottom-up或top-down任意一种方式。如果选用bottom-up,按照递推公式(性质1 or 2)计算出每个格子的值,从左到右计算第一行,然后计算第二行,以此类推。
T(n)=O(m*n)
【Step 2. 根据填满后的表格反推LCS】
在Step 1中如果遇到LCS性质1的情况,记录这个格子的位置,因为这代表这这个格子中的元素是LCS中的一部分。最后是通过逆序反推出来LCS中的每一个元素。
T(n)=O(m+n)
【T(n)】所以总共的T(n)=O(m*n)。

4. 一点心得:
DP vs. 贪心算法 vs. 分治
DP:分治的一种,子问题是重叠的。memoization是一种DP特有的、提高算法效率的方式。由于DP具有特征2:Overlapping subproblem,DP问题都可以加入memoization机制从而提高效率。
贪心算法:与DP有相似之处,也必须拥有特征1:Optimal structure。但是,子问题的最优解可以直接拿来用,不会"dynamic"。

======
大家好!我是一名转专业小白,对计算机算法感兴趣。我的背景是教育心理学,今年fall马上就要就读CS专业。
我发表这个帖子有两个目的,一是帮助我自己整理思路,还有一个目的是和大家交流分享~我希望可以帮助到和我一样正在努力转专业的同学们,也希望可以和大家和平交流。
谢谢:)






本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x

评分

参与人数 3大米 +9 收起 理由
不知道小帅 + 2 给你点个赞!
geniussmhd + 1 赞一个
14417335 + 6

查看全部评分


上一篇:关于刷题崩溃期 + 找工作的迷茫
下一篇:加米lc 270, 求问closest binary search tree value思路
我的人缘0

升级   23%

 楼主| liuzz10 2020-8-12 12:17:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (27)
 
 
0% (0)    👎
Code我是用的buttom up DP in Java。我把我出过的错(算是易错点)写到注解里了~
请见:https://leetcode.com/problems/lo ... th-buttom-up-DP.-It
回复

使用道具 举报

我的人缘0

升级   23%

 楼主| liuzz10 2020-8-13 06:09:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (27)
 
 
0% (0)    👎
Java vs Javascript comparison line by line: https://leetcode.com/problems/lo ... avascript-vs.-Java-(line-by-line)-oror-Buttom-up-DP-oror-For-beginners
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表