10066: The Twin Towers ★★★☆☆ 題組：Problem Set Archive with Online Judge

Presentation on theme: "10066: The Twin Towers ★★★☆☆ 題組：Problem Set Archive with Online Judge"— Presentation transcript:

1 10066: The Twin Towers ★★★☆☆ 題組：Problem Set Archive with Online Judge
解題者：黃俊騫 解題日期：2013年5月23日 題意：求兩數列的最長相同子數列(LCS)之長度。

2 題意範例：  4  6 解法： 令c[i,j]表示兩數列X = <x1, x2, …, xi>和Y = <y1, y2, …, yj> 最長相同子數列長度，則： 若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]開始算。 解法範例：見下頁

3 20 15 10 25

4 20 15 10 25 1

5 20 15 10 25 1

6 20 15 10 25 1

7 20 15 10 25 1

8 20 15 10 25 1

9 20 15 10 25 1

10 20 15 10 25 1

11 20 15 10 25 1

12 20 15 10 25 1

13 20 15 10 25 1

14 20 15 10 25 1 2

15 20 15 10 25 1 2

16 20 15 10 25 1 2

17 20 15 10 25 1 2 3 4

18 討論： (1) 暴力法的時間複雜度：O(m!×n!) (2) 動態規劃的時間複雜度：O(m×n) (3) m,n為兩數列的長度。