動(dòng)態(tài)規(guī)劃中的最長(zhǎng)公共子序列PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1動(dòng)態(tài)規(guī)劃中的最長(zhǎng)公共子序列動(dòng)態(tài)規(guī)劃中的最長(zhǎng)公共子序列第1頁(yè)/共15頁(yè)n 不一定。如不一定。如A, B與與B, An 本節(jié)的問(wèn)題是只找出一個(gè)最長(zhǎng)公共子序本節(jié)的問(wèn)題是只找出一個(gè)最長(zhǎng)公共子序列。列。第2頁(yè)/共15頁(yè)第3頁(yè)/共15頁(yè)第4頁(yè)/共15頁(yè)第5頁(yè)/共15頁(yè)第6頁(yè)/共15頁(yè)可以。這樣做不利于描述，如前面可以。這樣做不利于描述，如前面Xm1可以方便地表示可以方便地表示X前前m 1 個(gè)個(gè)元素，改元素，改后就比較麻煩。從遞歸的角度來(lái)看，后就比較麻煩。從遞歸的角度來(lái)看，一般也是從后面增減元素。一般也是從后面增減元素。第7頁(yè)/共15頁(yè)質(zhì)。質(zhì)。第8頁(yè)/共15頁(yè)第9頁(yè)/共15頁(yè)第10頁(yè)/共15頁(yè)X =

2、 A C B D Y = A B D A c b00000011110111101222012330000001331022220213302213ijxi=yj ci-1j=cij-111Y2N3N4Y21NY2NY第11頁(yè)/共15頁(yè)n1. X=B, C, A, D Y=C, A, B, D,求X與Y的最長(zhǎng)公共子序列，并畫(huà)出數(shù)組c與b. c b00000000110111101222012230000002213013220213302221i:j:第12頁(yè)/共15頁(yè)n1. X=B, C, A, D Y=C, A, B, D,求X與Y的最長(zhǎng)公共子序列，并畫(huà)出數(shù)組c與b. c b00000000110111101222012230000002213013220213302221i: 1 2 3j: 1 2 3 4 1 2 3 4 1 2 3 4第13頁(yè)/共15頁(yè)面向?qū)ο蟮木植縼?lái)看是結(jié)構(gòu)化的。面向?qū)ο蟮木植縼?lái)看是結(jié)構(gòu)化的。結(jié)構(gòu)化的基本思想是結(jié)構(gòu)化的基本思想是“自頂向下，逐步求精自頂向下，逐步求精”,面向?qū)ο蟮幕疽鈭D是提高軟件模塊的面向?qū)ο蟮幕疽鈭D是提高軟件模塊的復(fù)用性。復(fù)用性。純結(jié)構(gòu)化的程序編譯后基本上沒(méi)有多余的代純結(jié)構(gòu)化的程序編譯后基本上沒(méi)有多余的代碼，而面向?qū)ο蟮某绦蛴性S多。碼，而面向?qū)ο蟮某绦蛴性S多。面向?qū)ο笠詸C(jī)器的運(yùn)行復(fù)雜度換取