【刷题笔记】Leetcode #1143. Longest Common Subsequence

【题目】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专业。
我发表这个帖子有两个目的，一是帮助我自己整理思路，还有一个目的是和大家交流分享~我希望可以帮助到和我一样正在努力转专业的同学们，也希望可以和大家和平交流。
谢谢：）

Code我是用的buttom up DP in Java。我把我出过的错（算是易错点）写到注解里了~
请见：https://leetcode.com/problems/lo ... th-buttom-up-DP.-It

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