1樓：利丹寒
你把你的錯誤提示或者錯乎巨集誤答案貼出來呀鍵埋。printlcs(x,m,n,b);
lenghlcs(x,y,m,n,dp,b);
怎麼能先列印後求長度稿頃螞呢？
最長公共連續子序列和最長公共子序列
2樓：瀕危物種
最長公共序列：
a[1,3,5,2,5,3,4,5] 長度為m
b:[3,4,2,1,5] 長度為n
則它們的最長公共子序列為3,2,5
我旦餘們用lcs（xi,yj）來表示xi和yj的最長公共子序列的長度。
那麼當xi = yj時，我們就可以把xi和yj都往前移動一步來進行探索。
即lcs（模唯滾xi,yj） =lcs（xi-1,yj-1）+1
如果不相等，則要麼把x往前移動一步，要麼把y往前移動一步，看誰更大。
即lcs(xi,yj) =max(lcs（xi-1,yj）,lcs(xi,yj-1))
綜上if xi ==yj:
lcs（xi,yj） =lcs（xi-1,yj-1）+1
else:lcs(xi,yj) =max(lcs（xi-1,yj）,lcs(xi,yj-1))
如果要求這個最長子序列是什麼。
那麼我們就追根溯源。
i = m-1 ,j = n-1
s = while i >=0 and j >=0: #只要有乙個為0就停止。
if xi ==yj:
s +=xi
else:if lcs（xi-1,yj）>lcs（xi,yj-1）:
i -=1else:
j -=1return s[::1]
-如果是連續子序列問題。
我們就換個思路，山廳我們的關注點就應該在連續上面。
其實畫乙個m*n的矩陣，只有在連續的這些對角線上才有值，且值是遞增的。
所以，我們可以用乙個不一樣的角度的dp方程來表達。
dp[i][j] =0 如果i ==0 and j ==0
dp[i][j] =dp[i-1][j-1] +1 xi ==yj
dp[i][j] =0 xi !=yj
誰給個求最長公共子序列的演算法？
3樓：網友
首先告訴你個叫pyx1997的人。他教會了我，現在讓我來教會你。
我們來看一組資料：
好，讓我們手動計算一下：
如果我們純貪心的話：高個i變數直接從頭到尾迴圈：到i=2時，就求得maxlen=，maxlen被更新為3。
但是我們看得出：最長不降子序列為40 50 60 70，maxlen=4。
為什麼，為什麼貪心會導致如此結果？那就是因為貪心童鞋的生理缺陷：目光短淺！
好了，讓我們在重新審題。
此時因為我們的最長不降子序列同時要求「最長」和「不降」這兩個方面，又因為我們的眼光要放長遠，所以我們選擇了用乙個陣列來記錄以當前為起點的最長不降子序列。醬紫的話，我們就把這個大問題分成來若干個小問題。又因為如果我們順退的話，我們不能確定到底是怎麼樣才算最長，前面的長度總是依賴於後面的長度。
所以我們選擇倒推。
a:原始資料的存放陣列。
f:狀態陣列，即為以i(1<=i<=n)為起點的最長不降子序列的長度。不用設初值。
由於我不知道lz使用的是什麼語言，所以這裡給出偽**：
for i←n downto 1 //dp的次數。
maxlen←0 //將maxlen置空。
for j←n downto i+1 //二重迴圈：比較i後的已知的最長不降子序列的長度。
if (f[j]>maxlen)&(a[i]>=a[j]) then maxlen←f[j] /求出最大值。
f[i]←maxlen+1] /將最大值+1放入f[i]
然後，我們再將f陣列掃瞄一遍，取最大值，即為答案。
演算法描述完畢。具體的細節請自行除錯。本人打的很辛苦，望lz給分。
最長公共子序列的介紹
4樓：若兒蝵鮙笘
乙個數列 ，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則 稱為已知序列的最長公共子序列。
最長公共子序列的演算法
5樓：血盟孑孑
動態規劃的乙個計算兩個序列的最長公共子序列的方法如下：
以兩個序列 x、y 為例子：
設有二維陣列f[i,j] 表示 x 的 i 位和 y 的 j 位之前的最長公共子序列的長度，則有：
f[1][1] =same(1,1);
f[i,j] =max
其中，same(a,b)當 x 的第 a 位與 y 的第 b 位相同時為「1」，否則為喊公升前「0」。
此時，二維陣列中最大的數便是 x 和 y 的最長公共子序列的長度，鄭清依據該陣列回溯，便可找出最長公共子序笑源列。
該演算法的空間、時間複雜度均為o(n^2)，經過優化後，空間複雜度可為o(n)。
最長公共子序列的應用
6樓：彎弓弓彎弓
最長公共子序列是乙個十分實用的問題，它可以描述兩段文字之間的「相似度」，即它們的慶消雷同程度，從而能夠用來辨別抄襲譽沒知。對一段文字進行修改之後，計算察公升改動前後文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準確。簡而言之，知道、百科都用得上。
求陣列的最大子陣列值和最長公共子序列問題
7樓：司馬刀劍
a) 最長公共子序列的結構。
易證最長公共子序列問題也有最優子結構性質。
設序列x=和y=的乙個最長公共子序列z=，則：
i. 若xm=yn，則zk=xm=yn且zk-1是xm-1和yn-1的最長公共子序列；
ii. 若xm≠yn且zk≠xm ，則z是xm-1和y的最長公共子序列；
iii. 若xm≠yn且zk≠yn ，則z是x和yn-1的最長公共子序列。
其中xm-1=，yn-1=，zk-1=。
最長公共子序列問題具有最優子結構性質。
求最長公共子序列
8樓：匿名使用者
遞迴方法求最長公共子序列的長度。
1)設有字串a[0...n]，b[0...m]，下面就是遞推公式。
當數辯槐櫻組a和b對應位置攜叢字元明友相同時，則直接求解下乙個位置；當不同時取兩種情況中的較大數值。
C語言小白問題，求兩個字串的最長公共英文單詞
看不誒 呵呵 這些都不知道怎麼回事 不過我可以給你乙個建議 既然是兩句話中取最長的單詞 那麼你先擷取單詞 然後儲存到兩個變數中,進行比較 一組中最長的和另外一組中最長的進行比較就完成了 還能輸出最長的是哪個單詞,在哪句話中 c語言問題，小白求教 x y z的結果是這麼算的，先算x y,13大於8，結...
我與家長公共文明徵文,《我與家長共文明》作文800字
當前,我市建立全國文明城市工作正在如火如荼開展,營造文明 和諧 優美 舒適的城市環境既是廣大市民的共同願望,也是每位公民的責任.加強未成年人思想道德建設是建立全國文明城市的重要內容.今年以來,我們在市委 市 和省會文明委指導下,圍繞立德樹人根本任務,以 善行河北 首善省會 為主線,突出 中國夢 主題...
統計字串中最長單詞的長度！C語言
if str i a str i z 這句有點問題,z和a之間還有一些字元,應該排除掉 這個程式的主要問題是當讀到最後乙個字元null時,for迴圈退出,這時,count的值對應最後乙個單詞,而這時這個單詞的長度沒有進入for中的else進行比較,從而max的值會不對.所以你再在for後面加幾句 比...