python實(shí)現(xiàn)最長公共子序列
最長公共子序列python實(shí)現(xiàn)，最長公共子序列是動(dòng)態(tài)規(guī)劃基本題目，下面按照動(dòng)態(tài)規(guī)劃基本步驟解出來。
1.找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征
序列a共有m個(gè)元素，序列b共有n個(gè)元素，如果a[m-1]==b[n-1]，那么a[:m]和b[:n]的最長公共子序列長度就是a[:m-1]和b[:n-1]的最長公共子序列長度+1；如果a[m-1]!=b[n-1]，那么a[:m]和b[:n]的最長公共子序列長度就是MAX（a[:m-1]和b[:n]的最長公共子序列長度，a[:m]和b[:n-1]的最長公共子序列長度）。
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ì)算公共子序列長度的，可以看到最長是4；第二個(gè)矩陣是構(gòu)造這個(gè)最優(yōu)解用的；最后輸出一個(gè)最優(yōu)解BCBA。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
下面小編就為大家?guī)硪黄狿ython縮進(jìn)和冒號(hào)詳解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-06-06
井字棋（Tic-Tac-Toe）是一種經(jīng)典的兩人棋盤游戲,通常由兩名玩家輪流下棋,目標(biāo)是在一個(gè)3x3的棋盤上先形成橫向、縱向或?qū)蔷€的三個(gè)棋子,本文將介紹如何使用 Python 制作一個(gè)簡單的井字棋游戲、包括游戲規(guī)則、界面設(shè)計(jì)和實(shí)現(xiàn)代碼,需要的朋友可以參考下2023-11-11
Python入門Anaconda和Pycharm的安裝和配置詳解
這篇文章主要介紹了Python入門Anaconda和Pycharm的安裝和配置詳解，文章通過圖文介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
對pyqt5中QTabWidget的相關(guān)操作詳解
今天小編就為大家分享一篇對pyqt5中QTabWidget的相關(guān)操作詳解，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-06-06
python 遍歷列表提取下標(biāo)和值的實(shí)例
今天小編就為大家分享一篇python 遍歷列表提取下標(biāo)和值的實(shí)例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-12-12
Python+OpenCV實(shí)現(xiàn)信用卡數(shù)字識(shí)別的方法詳解
這篇文章主要介紹了如何利用python?opencv實(shí)現(xiàn)信用卡數(shù)字識(shí)別，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-09-09
Python中 CSV格式清洗與轉(zhuǎn)換的實(shí)例代碼
這篇文章主要介紹了Python123 CSV格式清洗與轉(zhuǎn)換的實(shí)例代碼，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-08-08
Python中使用socket發(fā)送HTTP請求數(shù)據(jù)接收不完整問題解決方法
這篇文章主要介紹了Python中使用socket發(fā)送HTTP請求數(shù)據(jù)接收不完整問題解決方法,本文使用一個(gè)循環(huán)解決了數(shù)據(jù)不完整問題,需要的朋友可以參考下2015-02-02
利用python如何處理百萬條數(shù)據(jù)(適用java新手)
這篇文章主要給大家介紹了關(guān)于利用python如何處理百萬條數(shù)據(jù)的相關(guān)資料，本文的教程非常適用于java新手，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考借鑒，下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-06-06
Python函數(shù)式編程指南（二）：從函數(shù)開始
這篇文章主要介紹了Python函數(shù)式編程指南（二）：從函數(shù)開始,本文講解了定義一個(gè)函數(shù)、使用函數(shù)賦值、閉包、作為參數(shù)等內(nèi)容,需要的朋友可以參考下2015-06-06