# [資演] 動態規劃 (II): 最長共同子序列

###### tags: `資演`

這邊我們介紹另一個動態規劃的經典問題：最長共同子序列（Longest Common Subsequence, LCS）。

## 問題
最長共同子序列問題指的是在兩個array裡面找出所有共同的子序列中**最長的子序列的長度**。子序列和subarray不同的地方在於：子序列不需要在原本的array中占用連續的位置，只需要保持前後的相對順序，中間可以夾雜別的元素。

舉例來說，我們現在有兩個array $S_1$ 和 $S_2$：
$$\begin{split}
S_1 &= [2,5,7,9,4,1,3]\\
S_2 &= [3,5,4,5,7, 3]
\end{split}
$$則他們的LCS是：
$$
\text{LCS} (S_1, S_2) = [5,4,3]
$$
## 解法
我們知道動態規劃有兩個要素：
* 最佳子結構（optimal substructure）
原問題可以分解成更小，更簡單的「子問題」，而這個子問題可以進一步分解成更小的子問題。
* 重疊子問題（overlapping subproblem）
子問題的解是可以重複使用的，也就是說，較高階的子問題（在遞迴樹上較接近root的問題）通常會重複使用低階子問題（在遞迴樹上較接近葉子的問題）的解。

有了這兩個要素，就代表原問題可以使用動態規劃來對時間複雜度來進行優化。

那要怎麼看出這個問題滿足這些要素呢？首先我們必須先使用divide and conquer來找出一個遞迴暴力解，所以最重要的是要如何對這個原問題進行**分割**。

假設有二個array為 $S_1$ 和 $S_2$，其**最長共同子序列**（LCS）表示為 $\text{LCS} (S_1, S_2)$。$S_1$ 和 $S_2$ 的最後一個元素分別以 $e_1$ 與 $e_2$ 表示，剩餘部分以 $S'_1$ 與 $S'_2$ 表示，也就是說：
$$\begin{split}
S_1&=S'_1+e_1\\
S_2&=S'_2+e_2
\end{split}
$$根據上面的表示，我們可以將 $S_1$ 與 $S_2$ 的LCS分為以下幾種情形：
* LCS 包含 $e_1$ 但不包含 $e_2$
此種情形 $e_2$ 沒有用處，若要找到 LCS 只需要從 $S'_2$ 去找：
$$
\text{LCS} (S_1, S_2) = \text{LCS} (S_1, S'_2)
$$
* LCS 包含 $e_2$ 但不包含 $e_1$
此種情形 $e_1$ 沒有用處，若要找到 LCS 只需要從 $S'_1$ 去找。
$$
\text{LCS} (S_1, S_2) = \text{LCS} (S'_1, S_2)
$$
* LCS 不包含 $e_1$ 也不包含 $e_2$
此種情形 $e_1$ 和 $e_2$ 都沒有用處，若要找到 LCS 只需要從 $S'_1$ 和 $S'_2$ 去找：
$$
\text{LCS} (S_1, S_2) = \text{LCS} (S'_1, S'_2)
$$
* LCS 包含 $e_1$ 也包含 $e_2$
此種情形 LCS 同時包含 $e_1$ 和 $e_2$，且 $e_1$ 和 $e_2$ 分別為2個array的最後一個元素，並且 $e_1=e_2$，也就是說，LCS 的最後一個元素必定為 $e_1$ (也就是 $e_2$)：
$$
\text{LCS} (S_1, S_2) = \text{LCS} (S'_1, S'_2) + 1
$$

另外我們也考慮到一個base case：當 $S_1$ 或 $S_2$ 是空的array時，LCS也是空的。

這裡我們可以建立一個表格`dp`，其中`dp[i][j]`這個元素代表的意思是`s1[0:i]`和`s2[0:j]`這兩個 subarray 的 LCS 長度。

根據以上邏輯，我們可以將演算法寫成Python code如下：

def lcs(s1, s2):
    n1 = len(s1)
    n2 = len(s2)

    dp = [[None] * (n2 + 1) for i in range(n1 + 1)]

    for i in range(n1 + 1):
        for j in range(n2 + 1):
            if i == 0 or j == 0 :
                dp[i][j] = 0
            elif s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                
    return dp[m][n]