亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

動態規劃經典例題——最長公共子序列和最長公共子串(python)

系統 2269 0

1. 最長公共子序列(LCS)

1.1 問題描述

動態規劃經典例題——最長公共子序列和最長公共子串(python)_第1張圖片

1.2 思路

利用動態規劃。
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第2張圖片
下一步就要找到狀態之間的轉換方程。
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第3張圖片
因此可以根據這個方程來進行填表,以"helloworld"和“loop”為例:
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第4張圖片

1.3 Python代碼

            
              
                def
              
              
                LCS
              
              
                (
              
              string1
              
                ,
              
              string2
              
                )
              
              
                :
              
              
    len1 
              
                =
              
              
                len
              
              
                (
              
              string1
              
                )
              
              
    len2 
              
                =
              
              
                len
              
              
                (
              
              string2
              
                )
              
              
    res 
              
                =
              
              
                [
              
              
                [
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              len1
              
                +
              
              
                1
              
              
                )
              
              
                ]
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              len2
              
                +
              
              
                1
              
              
                )
              
              
                ]
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
              len2
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
              len1
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                if
              
               string2
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                ==
              
               string1
              
                [
              
              j
              
                -
              
              
                1
              
              
                ]
              
              
                :
              
              
                res
              
                [
              
              i
              
                ]
              
              
                [
              
              j
              
                ]
              
              
                =
              
               res
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                [
              
              j
              
                -
              
              
                1
              
              
                ]
              
              
                +
              
              
                1
              
              
                else
              
              
                :
              
              
                res
              
                [
              
              i
              
                ]
              
              
                [
              
              j
              
                ]
              
              
                =
              
              
                max
              
              
                (
              
              res
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                [
              
              j
              
                ]
              
              
                ,
              
              res
              
                [
              
              i
              
                ]
              
              
                [
              
              j
              
                -
              
              
                1
              
              
                ]
              
              
                )
              
              
                return
              
               res
              
                ,
              
              res
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                [
              
              
                -
              
              
                1
              
              
                ]
              
              
                print
              
              
                (
              
              LCS
              
                (
              
              
                "helloworld"
              
              
                ,
              
              
                "loop"
              
              
                )
              
              
                )
              
              
                # 輸出結果為:
              
              
                [
              
              
                [
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ]
              
              
                ,
              
              
                [
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ]
              
              
                ,
              
              
                [
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                2
              
              
                ,
              
              
                2
              
              
                ,
              
              
                2
              
              
                ,
              
              
                2
              
              
                ,
              
              
                2
              
              
                ,
              
              
                2
              
              
                ]
              
              
                ,
              
              
                [
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                2
              
              
                ,
              
              
                2
              
              
                ,
              
              
                3
              
              
                ,
              
              
                3
              
              
                ,
              
              
                3
              
              
                ,
              
              
                3
              
              
                ]
              
              
                ,
              
              
                [
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                0
              
              
                ,
              
              
                1
              
              
                ,
              
              
                1
              
              
                ,
              
              
                2
              
              
                ,
              
              
                2
              
              
                ,
              
              
                3
              
              
                ,
              
              
                3
              
              
                ,
              
              
                3
              
              
                ,
              
              
                3
              
              
                ]
              
              
                ]
              
              
                ,
              
              
                3
              
            
          

所以"helloworld"和"loop"的最長公共子序列的長度為3。

1.4 找到具體的子序列

下面的內容借鑒了博主Running07的博客動態規劃 最長公共子序列 過程圖解

如果有兩個字符串如下:
S1 = “123456778”
S2 = “357486782”
其最終的動態規劃填表結果為:
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第5張圖片
其中S1和S2的LCS并不是只有1個。
我們根據遞歸公式:
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第6張圖片
構建了上表,
通過遞推公式,可以看出,res[i][j]的值來源于res[i-1][j]或者是res[i-1][j]和res[i][j-1]的較大值( 可能相等 )。
我們將從最后一個元素c[8][9]倒推出S1和S2的LCS。
res[8][9] = 5,且S1[8] != S2[9],所以倒推回去,res[8][9]的值來源于c[8][8]的值(因為res[8][8] > res[7][9])。
res[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去,res[8][8]的值來源于 res[7][7]。
以此類推,如果遇到S1[i] != S2[j] ,且res[i-1][j] = res[i][j-1] 這種存在分支的情況,這里都選擇一個方向(之后遇到這樣的情況,也選擇相同的方向,要么都往左,要么都往上)。
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第7張圖片
可得S1和S2的LCS為{3、5、7、7、8} 這是遇見相等的時候,統一往左走
S1和S2之間還有一個LCS 這是遇見相等的時候,統一往上走
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第8張圖片
可得S1和S2的LCS為{3、4、6、7、8}

2. 最長公共子串

2.1 問題描述

動態規劃經典例題——最長公共子序列和最長公共子串(python)_第9張圖片

2.2 思路

和最長公共子序列一樣,使用動態規劃的算法。
下一步就要找到狀態之間的轉換方程。 動態規劃經典例題——最長公共子序列和最長公共子串(python)_第10張圖片
和LCS問題唯一不同的地方在于當A[i] != B[j]時,res[i][j]就直接等于0了,因為子串必須連續, 且res[i][j] 表示的是以A[i],B[j]截尾的公共子串的長度 。因此可以根據這個方程來進行填表,以"helloworld"和“loop”為例:
動態規劃經典例題——最長公共子序列和最長公共子串(python)_第11張圖片
這個和LCS問題還有一點不同的就是,需要設置一個res,每一步都更新得到最長公共子串的長度。

2.3 Python代碼

            
              
                def
              
              
                LCstring
              
              
                (
              
              string1
              
                ,
              
              string2
              
                )
              
              
                :
              
              
    len1 
              
                =
              
              
                len
              
              
                (
              
              string1
              
                )
              
              
    len2 
              
                =
              
              
                len
              
              
                (
              
              string2
              
                )
              
              
    res 
              
                =
              
              
                [
              
              
                [
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              len1
              
                +
              
              
                1
              
              
                )
              
              
                ]
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              len2
              
                +
              
              
                1
              
              
                )
              
              
                ]
              
              
    result 
              
                =
              
              
                0
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
              len2
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                for
              
               j 
              
                in
              
              
                range
              
              
                (
              
              
                1
              
              
                ,
              
              len1
              
                +
              
              
                1
              
              
                )
              
              
                :
              
              
                if
              
               string2
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                ==
              
               string1
              
                [
              
              j
              
                -
              
              
                1
              
              
                ]
              
              
                :
              
              
                res
              
                [
              
              i
              
                ]
              
              
                [
              
              j
              
                ]
              
              
                =
              
               res
              
                [
              
              i
              
                -
              
              
                1
              
              
                ]
              
              
                [
              
              j
              
                -
              
              
                1
              
              
                ]
              
              
                +
              
              
                1
              
              
                result 
              
                =
              
              
                max
              
              
                (
              
              result
              
                ,
              
              res
              
                [
              
              i
              
                ]
              
              
                [
              
              j
              
                ]
              
              
                )
              
              
                return
              
               result

              
                print
              
              
                (
              
              LCstring
              
                (
              
              
                "helloworld"
              
              
                ,
              
              
                "loop"
              
              
                )
              
              
                )
              
              
                # 輸出結果為:2
              
            
          

更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 仑乱高清在线一级播放 | 四虎永久在线观看免费网站网址 | 久久99精品久久久久子伦小说 | 久久久婷婷亚洲5月97色 | 曰本性l交片视频视频 | 午夜精品久久久 | 日韩最新视频一区二区三 | 国产麻豆精品aⅴ免费观看 国产麻豆精品hdvideoss | 亚洲国产一区二区三区最新 | 成人免费毛片一区二区三区 | 色老头福影院韩国激情影院 | 国产老年人性视频 | 国产一级视频久久 | 欧美日韩中文在线视频 | 日韩毛片大全 | 91粉色视频在线观看 | 夜夜摸视频网 | 大乳女做爰中文字幕 | 亚洲福利一区二区 | 亚洲在线视频免费观看 | 日本一级毛片一级裸片 | 亚洲国产模特在线播放 | 香蕉依依精品视频在线播放 | 欧美视频性 | 亚洲一区二区三区久久久久 | 看全色黄大色黄大片色责看的 | 欧美国产激情二区三区 | a级毛片视频 | 三级性生活视频 | 精品一本久久中文字幕 | 日本在线视频精品 | 欧美日韩在线看 | 日日碰狠狠添天天爽爽爽 | 可以免费观看欧美一级毛片 | 一级黄毛片 | www.黄色一片 | 国产xxxx69免费大片 | 久久精品视频一区 | 国产爆操| 美国黄色大片 | 神马影院我不卡在线观看 |