Re: [理工] Longest Common Subsequence (LCS)演算法

[LoveYT1213 (995)]

※ 引述《ken1325 (為愛瘦一次)》之銘言：
: 我是看演算法筆記：http://tinyurl.com/yk2s669
: 在 Longest Common Subsequence:
: Dynamic Programming 的部份
: 我的問題如下圖：http://ppt.cc/ozNl
: 請問他是怎麼簡化的？
: 感謝回答

集合論問題吧!

s1 = sub1 + e1

s2 = sub2 + e2
-----------------------------------------------------------
狀況1 => LCS(sub1,s2)  ----- 代表e1 不在LCS內

狀況2 => LCS(sub2,s1)  ----- 代表e2 不在LCS內

狀況3 => LCS(sub1,sub2)----- 代表e1 及 e2 不在LCS內
-----------------------------------------------------------
LCS 取最長的

所以 max{狀況1,狀況2} 就已經包含狀況3了

可以簡化~

我的理解上是這樣~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.254.243.243
→ ken1325:感謝