home · Posts · Archive · Tags

20180205-uva10405

#uva

#心得 #Longest_Common_Subsequence #LCS #DP #Uva10405 #解題

心得：

這題其實看懂題目+用陣列來填真的蠻簡單，但是我debug了一天，因為我圖表陣列的型別弄錯QQ 要注意這個陣列是int

題目：找最長的共同子集合

分析：

先了解甚麼是共同子集合

以

{ a,b,c,d}
來說

{ b, c }
是他的子集合

{ c, b }
就不是

假設兩個序列 c1,c2

假設c1中存在一個a

你就是要去c2中找有沒有a，

找到了之後再找c1中的下一個字母

而DP其實就是

  • 把大問題切成很多很多重複的小問題

  • 也可以用特定計算(遞迴)求出來

  • 把算過的答案計算下來

以這題來講，

我們用

lcs[i+1][j+1]
來記下算過的答案。

我們最後的答案會在

lcs[m][n]
，因為此時我們已經掃完c1與c2的所有元素

每當我在c2裡找到原本c1的下一個子元素，

我就會把值+1，來代表他的子元素的長度。

如果我還沒有在c2中找到c1中我要找的元素，就把我之前找到的和我之前記下來的答案取最大值(max)，這個步驟我覺得其實講成白話文就是記下我之前找到的最長子集合長度

為甚麼我填值是從

lcs[i+1][j+1]
是因為我要讓 第i行 與 第j列保持都是0，這樣讓我在找max的時候會比較好算

這題要畫圖比較好理解

Ref

 👈Go Back

@alanhc