10066: The Twin Towers ★★★☆☆ 題組：Problem Set Archive with Online Judge 解題者：黃俊騫 解題日期：2013年5月23日 題意：求兩數列的最長相同子數列(LCS)之長度。
題意範例：20 15 10 15 25 20 15 15 25 10 20 15 20 4 10 20 20 10 20 10 20 10 20 10 20 10 10 20 10 10 20 6 解法： 令c[i,j]表示兩數列X = <x1, x2, …, xi>和Y = <y1, y2, …, yj> 最長相同子數列長度，則： 0 若i=0或j=0 c[i,j]= c[i-1,j-1]+1 若i,j>0且xi=yj max(c[i,j-1],c[i-1,j]) 若i,j>0且xi≠yj 動態規劃，從c[1,1]開始算。 解法範例：見下頁
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1 2
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1 2
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1 2
20 15 10 15 25 20 15 15 25 10 20 15 20 20 15 10 25 1 2 3 4
討論： (1) 暴力法的時間複雜度：O(m!×n!) (2) 動態規劃的時間複雜度：O(m×n) (3) m,n為兩數列的長度。