根據(jù)算法課總結(jié)。

最長(zhǎng)公共子序列是一種衡量?jī)蓚€(gè)string相似度的方式。

子序列（subsequence）是包含在string里的序列，它不需要連續(xù)，可間斷。

因?yàn)橐粋€(gè)string 有2^N個(gè)子序列，所以如果用窮舉法（brute force method），則需要O（2^N）次。

動(dòng)態(tài)規(guī)劃是可行的。

1. 這個(gè)問(wèn)題有最優(yōu)結(jié)構(gòu)（optimal structure）。

2. 有重疊的子問(wèn)題（overlapping subproblems）。

3. Θ（MN）

java 代碼，兩種方法。

重建LCS

performance