摘要: 既然已經(jīng)說到了最長公共子序列,就把這個遞增子序列也說了。同樣的,這里subsequence表明了這樣的子序列不要求是連續(xù)的。比如說有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }這樣一個字符串的的最長遞增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。
其實這個問題和前面的最長公共子序列問題還是有一定的關(guān)聯(lián)的。假設(shè)我們的初始的序列S1。那我們從小到大先排序一下。得到了S1'。這樣我們再球S1和S1'的最長公共子序列就可以知道答案了:)是不是有點巧妙啊。這個過程還是比較直觀的。但是這個不是這次要說的重點,這個問題有比較傳統(tǒng)的做法的.
我們定義L(j)是一個優(yōu)化的子結(jié)構(gòu),也就是最長遞增子序列.那么L(j)和L(1..j-1)的關(guān)系可以描述成
閱讀全文