python實(shí)現(xiàn)最長(zhǎng)公共子序列
最長(zhǎng)公共子序列python實(shí)現(xiàn)，最長(zhǎng)公共子序列是動(dòng)態(tài)規(guī)劃基本題目，下面按照動(dòng)態(tài)規(guī)劃基本步驟解出來(lái)。
1.找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征
序列a共有m個(gè)元素，序列b共有n個(gè)元素，如果a[m-1]==b[n-1]，那么a[:m]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度就是a[:m-1]和b[:n-1]的最長(zhǎng)公共子序列長(zhǎng)度+1；如果a[m-1]!=b[n-1]，那么a[:m]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度就是MAX（a[:m-1]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度，a[:m]和b[:n-1]的最長(zhǎng)公共子序列長(zhǎng)度）。
2.遞歸定義最優(yōu)值
3.以自底向上大方式計(jì)算出最優(yōu)值
python代碼如下：
def lcs(a,b):
lena=len(a)
lenb=len(b)
c=[[0 for i in range(lenb+1)] for j in range(lena+1)]
flag=[[0 for i in range(lenb+1)] for j in range(lena+1)]
for i in range(lena):
for j in range(lenb):
if a[i]==b[j]:
c[i+1][j+1]=c[i][j]+1
flag[i+1][j+1]='ok'
elif c[i+1][j]>c[i][j+1]:
c[i+1][j+1]=c[i+1][j]
flag[i+1][j+1]='left'
else:
c[i+1][j+1]=c[i][j+1]
flag[i+1][j+1]='up'
return c,flag
def printLcs(flag,a,i,j):
if i==0 or j==0:
return
if flag[i][j]=='ok':
printLcs(flag,a,i-1,j-1)
print(a[i-1],end='')
elif flag[i][j]=='left':
printLcs(flag,a,i,j-1)
else:
printLcs(flag,a,i-1,j)
a='ABCBDAB'
b='BDCABA'
c,flag=lcs(a,b)
for i in c:
print(i)
print('')
for j in flag:
print(j)
print('')
printLcs(flag,a,len(a),len(b))
print('')
運(yùn)行結(jié)果輸出如下：
4.根據(jù)計(jì)算最優(yōu)值得到的信息，構(gòu)造最優(yōu)解
上圖是運(yùn)行結(jié)果，第一個(gè)矩陣是計(jì)算公共子序列長(zhǎng)度的，可以看到最長(zhǎng)是4；第二個(gè)矩陣是構(gòu)造這個(gè)最優(yōu)解用的；最后輸出一個(gè)最優(yōu)解BCBA。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了Win10+GPU版Pytorch1.1安裝的安裝步驟，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
使用Python連接Elasticsearch服務(wù)器進(jìn)行數(shù)據(jù)搜索和分析是一項(xiàng)常見(jiàn)操作,本文詳細(xì)介紹了如何使用elasticsearch-py客戶(hù)端庫(kù)連接到Elasticsearch服務(wù)器,并執(zhí)行創(chuàng)建索引、添加文檔及搜索等基本操作2024-10-10
在本篇文章里小編給大家分享的是關(guān)于Python pandas用法以及相關(guān)實(shí)例代碼，需要的朋友們可以學(xué)習(xí)下。2019-08-08
Python實(shí)現(xiàn)判斷變量是否是函數(shù)方式
這篇文章主要介紹了Python實(shí)現(xiàn)判斷變量是否是函數(shù)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-02-02
關(guān)于Python下的Matlab函數(shù)對(duì)應(yīng)關(guān)系(Numpy)
這篇文章主要介紹了關(guān)于Python下的Matlab函數(shù)對(duì)應(yīng)關(guān)系(Numpy)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
python實(shí)現(xiàn)簡(jiǎn)單井字棋游戲
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)簡(jiǎn)單井字棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了淺析python字符串前加r、f、u、l 的區(qū)別,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-01-01
基于python+selenium的二次封裝的實(shí)現(xiàn)
這篇文章主要介紹了基于python+selenium的二次封裝的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01
這篇文章主要介紹了python中使用.py配置文件的方法，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11
python實(shí)現(xiàn)雙人版坦克大戰(zhàn)游戲
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)雙人版坦克大戰(zhàn)游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12