# 麻省理工學院公開課-算法導論_第十四講-動態規劃與最長共同子序列
###### tags: `MIT` `Algorithms` `網易`

[課程連結](http://open.163.com/newview/movie/free?pid=M6UTT5U0I&mid=M6V2U1HL4)

## Dynamic programming

這邊所指的programming並非指程式，而是它本質所指的意義，也就是按一定的步驟來解決問題。它是一種設計的技巧，就好比先前說過的divided and conqure，是一種解決問題的方法，而不是某一個固定的演算法。

課程中會用Longest Common Subsequence Problem(最長共同子序列，亦稱LCS)來說明。這在生物學很長用，像是DNA，我們希望找到兩個DNA中相同的基因序列。

給出兩個序列，其中$x=[1 ... m], y=[1 ... n]$，找出它們的LCS，通常這不會有唯一解。


假設，
x: A B C B D A B
y: B D C A B A

那LCS(x, y) = BDAB、BCAB、BCBA

或許我們可以用窮舉法來暴力解，看每一個x內的子序列是否也存在y裡面。


我們要分析暴力解需要多少時間來處理：
1. 給定一個x內的子序列，需要花多少時間來確定這個子序列是否也存在y裡面?答案是$O(n)$，因為不管怎麼樣你就是需要掃描一次y裡面的所有資料
2. 那x的序列可以有幾種子序列?答案是$2^m$個

現在我們知道，當這個問題是worst case的時候，需要的時間會是$O(n \cdot 2^m)$，這非常的慢。

## Simplification

剛剛我們看到，整個時間是呈現指數型成長，那非常的糟糕，所以我們要來簡化這個作業流程：
1. 首先找出LCS(x, y)的長度
2. 擴展這個演算法來找出它們本身的LCS

最長的長度就只會有一個，我們先確定長度，就不需要考慮其它的長度的因素，這就相對的簡化了問題，在第一步工作就只需要記下最大長度的問題，那就變成一個找數值的問題。

我們使用的策略就是，考慮x、y的前綴(prefix)，然後用這個prefix來描述LCS的長度，我們用$c[i, j]$來表示$\vert LCS(x[1, i], y[1, j]) \vert$的prefix的長度，那麼$C[i, j]=\vert LCS(x, y) \vert$，因為這代表1~m、1~n都走過一遍了。

符號說明，當用絕對值包住序列的時候，$\vert S \vert$，即代表序列$S$的長度。
## Theorem

現在，就可以開始來找出$c[i, j]$：
$$
c[i, j] =
\begin{cases}
c[i-1, j-1] + 1, & \text{if $x[i]=y[j]$} \\[2ex]
\max\{c[i, j-1], c[i-1, j] \}, & \text{otherwise}
\end{cases}
$$

給定兩個序列，$x=[1 ... m], y=[1 ... n]$，下面證明為什麼上面的公式可以找出LCS，首先說明當$x[i]=y[j]$。


假設，當$c[i, j] = k$，那麼$z[1 ... k]=LCS(x[1 ... i], y[1 ... j])$，那麼$z[k]=x[i](=y[j])$，回看上面黑板畫的那個序列，假設，兩個相等的字符($x[i]=y[j]$)目前是不存在的，在碰到它們的時候就可以把值寫入LCS，也就是$z[k]$，所以$z[k]$才會等於$x[i]$或是$y[j]$。

很明顯的，$z[1 ... k-1]$就會是$LCS(x[1..i-1], y[1..j-1])$。這不難想像，如果現在的$LCS=ABD$，而這個是因為你已經看到$x[i]$與$y[j]$，因此$LCS(x[i-1], y[j-1])=AB$就一定是成立的，因為$D$的出現是因為看到$i, j$兩個索引才有的。


這邊要證明上面的論調，假設，$w$是一個更長的common sequence，也就是$\vert w \vert > k-1$。

我們用cut and paste argument(複製貼上?)，將$w$與$z[k]$兩個字串合併，也就是$w \vert \vert z[k]$，這個合併後的common sequence一定會是$x[1..i], y[1..j]$的其中一個command sequence，而且長度一定大於k，因為$w$的長度已經大於$k-1$，但這個推論是矛盾的。

因此，$c[i-1, j-1]=k-1$，而$c[i, j]=c[i-1, j-1]+1$

這邊的說明其實不是很懂，只能另外找資料研究一下。

## Dynamic programming hallmark

Dynamic programming的一個特性，Optimal substructure，意謂著一個問題的最佳解包含著其子問題的最佳解。

舉例來說，上面的LCS問題，如果$z=LCS(x, y)$，這意謂著$z$同時是$x, y$的prefix。

## Recursive alg for LCS

LCS(x, y, i, j) //ignoring base cases
  if x[i] = y[j]
    then c[i, j] <- LCS(x, y, i-1, j-1) + 1
    else c[i, j] <- max {LCS(x, y, i-1, j), LCS(x, y, i, j-1)}
  
  return c[i, j]

這個問題的worse case會發生在$x[i] \neq y[j] \space \forall \space i, j$


上面是這個問題的recursion tree的說明，tree的高度為$m+n$，直觀來想，你終究還是可能會把兩個陣列的所有值都順過一次，很明顯的這樣的工作量會以指數型成長，意謂著會非常的慢。

不過可以發現到一件事，這整個遞迴樹的計算有很多是重覆計算的(見黑板圈圈)，這意謂著有相同的子問題，也說明著有很多的重覆性的工作，那我們怎麼樣可以不要做重覆性的工作?

這時候dynamic programming的第二個特性就出現了。

## Dynamic programming hallmark Second

Overlapping subproblems，意謂著遞迴過程中有部份的子問題被重覆的計算多次。

上面的LCS問題總共有$m \cdot n$個子問題，雖然相比那指數型的工作量這顯得有點微不足道，

## Memorization alg

針對LCS的問題，我們可以採用Memoization的方式，注意，是memo，不是memory，也就是你在處理子問題的時候你可以記錄一下"這個子問題我計算過了喔"，當後面需要計算相同子問題的時候，我們就不需要再計算，直接拿這個計算過的結果來用就可以。

上面給出的程式碼大致跟先前的一樣，就只有多一個判斷，判斷$c[i, j]$是否為空，是，那才計算，不然我就直接回傳計算過的結果就可以。


很神奇的，在這麼做之後它的時間複雜度變成$\Theta(mn)$，不去想複雜的推論，直觀來想，最少最少每次的$c[i, j]$都還是會計算一次，碰到有的就直接回傳。空間複雜度來看，我們也只需要$\Theta(mn)$，就只是記錄$c[i, j]$的值。

但這麼做還是會有一些的缺點，不過還是會有一種方法可以處理，從遞迴的角度來看，那是一種由上而下的展開，那如果我們改變一下想法，變成由下往上呢?這種由下往上的思維就是真正的Dynamic program。


上面是一個推論的過程，週邊取最大值的概念，不難理解。圈起來的就是相同的，依著路徑我們就可以找到其中一個LCS，也就是BCBA。


整個時間複雜度如剛才所說的，就是$\Theta(mn)$。我們利用tracking backward的方式來Reconstruct LCS。也就是上一張簡報所看到的那樣，從最終的節點往上開始選徑回去。

空間複雜度來看也是$\Theta(mn)$，但其實可以做到$\Theta(min\{mn\})$，依著row或是column，逐一的來做，我們並不需要太多資訊，不過這邊解釋起來不是很清楚，只能找時間再理解。

Dynamic program與Memorization並不一樣，但它們之間是有關聯的。