動态規劃之最長公共子序列------2012年12月22日,23日

         今天是2012年12月22日。今天的算法練習題是最長公共子序列的長度求解。

         此題初看時，感覺問題非常複雜，要求解兩個序列的最長的(可以不連續)的公共子序列。但是，"将複雜的問題分解成簡單的問題"是基本的程式設計思想。分治法是将一個大問題分解成多個相似的小問題，而本題采用的動态規劃算法，則是将複雜的問題分解成一系列的相似的子問題。另外，将所求解的子問題的解通過數組等容器儲存起來，來節省重複求解相同子問題的時間，是動态規劃算法的一個很重要的思想:備忘錄思想。

         另外，本題還将采用逆向的思路，這與正常的順序的思路相悖。str1[a],str2[b]兩個字元串，不是從左至右的考慮，而是從右至左的方向。

         分析過程如下:

         str1[a],str1[b]是待求最長公共子序列的兩個字元串，假設result[c]就是其最長公共子序列。

         那麼就有以下3種情況。

         1.如果str1[a-1]==str2[b-1]，那麼肯定有result[c-1]=str1[a-1]=str2[b-1],即最後一個元素一定是最長公共子序列的一部分。那麼，就可以不再考慮str1[a-1],str2[b-1],result[c-1],從他們之前的元素開始讨論，也就是意味着，result[c-2]及之前的元素就是str1[a-2]之前的元素與str[b-2]之前的元素的最長公共子序列。

         2.如果str1[a-1]!=str2[b-1],而且result[c-1]!=str1[a-1]，那麼就可以肯定,str1[a-1]不在最長公共子序列中，也就是說，result[c-1]及之前的元素就是str1[a-2]之前的元素與str2[b-1]之前的元素的最長公共子序列。

         3.如果str1[a-1]!=str2[b-1],而且result[c-1]!=str2[b-1]，類似的，就可以肯定,str1[b-1]不在最長公共子序列中，也就是說，result[c-1]及之前的元素就是str1[a-1]之前的元素與str2[b-2]之前的元素的最長公共子序列。

         由此，可以得到遞歸方程。(ps:我不知道在這裡如何插入公式，如果您知道，請告訴小弟我，非常感謝!)

         max_len[i][j]=0                                      如果i<=0 || j<=0     (當一個序列長度為0時，也就沒有意義)

                            =1 +max_len[i-1][j-1]         如果str1[i-1]==str2[j-1]      (對應上面第1種情況)

                            =MAX(max_len[i-1][j],max_len[i][j-1])   如果str1[i-1]!=str2[j-1]     (對應上面第2,3種情況)

         思路已經很清晰了，代碼如下:

最長公共子序列

         明天得把具體的最長公共子序列給列印出來。

         以下内容補充于2012年12月23日:

          昨天留了個問題，就是列印出最長公共子序列。想了一會，沒什麼思路，就索性把max_len給列印出來，結果一列印我才發現，我把問題想得太複雜了。這本是一個多麼簡單的問題。

          比如str1="abbcd";  str2="afffbcd";  那麼列印出max_len:

<a href="http://www.cnblogs.com/NeilHappy/archive/2012/12/22/2829568.html#">?</a>

<code>1 0 0 0 0 0 0</code>

<code>0 0 0 0 0 0 0</code>

<code>0 0 0 0 2 0 0</code>

<code>0 0 0 0 0 3 0</code>

<code>0 0 0 0 0 0 4</code>

　　一目了然了。當且僅當str1[a-1]==str2[b-1]時，肯定會使得max_len中對應元素加1.

       在程式中加一步就可以了。如下:

         如果您覺得我的文章對您有所幫助，請贊一下，非常感謝!   

本文轉自NeilHappy 51CTO部落格，原文連結：http://blog.51cto.com/neilhappy/1097226，如需轉載請自行聯系原作者