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