算法設(shè)計(jì)與分析 課件 許瑾晨 第五章 動態(tài)規(guī)劃序

信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—序國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版

動態(tài)規(guī)劃（DynamicProgramming，DP）R.RichardBellman(1920~1984)20世紀(jì)50年代初，美國數(shù)學(xué)家理查德?貝爾曼等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動態(tài)規(guī)劃。

動態(tài)規(guī)劃的應(yīng)用非常廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事以及自動化控制等領(lǐng)域。問題引出兔子繁殖數(shù)字三角形原理和步驟兩個重要性質(zhì)最優(yōu)子結(jié)構(gòu)重疊子問題求解步驟（四步）典型應(yīng)用0-1背包矩陣連乘最長公共子序列最長不上升子序列編輯距離最優(yōu)二叉搜索樹信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—引例—兔子繁殖國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版兔子繁殖問題：

一對兔子從出生后第三個月開始，每月會生一對小兔子。如果兔子只生不死，一月份抱來一對剛出生的小兔子，問一年中每個月各有多少對兔子。F(n)表示第n個月的兔子對數(shù)，F(xiàn)(n)=上個月的兔子+本月新出生的兔子F(n-1)F(n-2)斐波納契數(shù)列（FibonacciSequence）F(n)=

1 ifn=0or1F(n-1)+F(n-2) ifn>11，1，2，3，5，8，11，19，30，49，……方法一：遞歸實(shí)現(xiàn)基于分治的遞歸實(shí)現(xiàn)：intF(intn){ if（n==0||n==1）return1; returnF(n-1)+F(n-2);}F(n)=F(n-1)+F(n-2)問題：該方法求解第n項(xiàng)的時間復(fù)雜度是多少？單選題。遞歸求解Fibonacci數(shù)列第n項(xiàng)的時間復(fù)雜度是多少？A.O(n)B.O(n2)C.O(2n)D.O(1)方法一：遞歸實(shí)現(xiàn)F(n)F(n-1)F(n-2)F(n-2)F(n-3)F(n-3)F(n-4)F(n-3)F(n-4)F(n-4)F(n-5)F(n-4)F(n-5)F(n-5)F(n-6)F(n)F(n-1)F(n-2)F(n-2)F(n-3)F(n-3)F(n-4)F(n-3)F(n-4)F(n-4)F(n-5)F(n-4)F(n-5)F(n-5)F(n-6)T(n)=T(n-1)+T(n-2)+1=O(2n)F(n)=F(n-1)+F(n-2)思考：時間復(fù)雜度高的原因是什么？原因：存在大量的重復(fù)計(jì)算。方法二：帶記憶的遞歸實(shí)現(xiàn)（備忘錄）去除重復(fù)計(jì)算的方法：保存計(jì)算結(jié)果/*A[i]表示第i個月的兔子對數(shù)，初始化為0*/intA[MAXSIZE]={0};intF(intn){

if(n==0||n==1)A[n]=1;elseif(A[n]==0)A[n]=F(n-1)+F(n-2);returnA[n];}T(n)=O(n)方法三：遞推實(shí)現(xiàn)intF(intn){

A[0]=A[1]=1;for(inti=2;i<=n;i++)A[i]=A[i-1]+A[i-2];returnA[n];}月份12345678兔子數(shù)1123581321A[8]A[6]A[7]+依然在內(nèi)存T(n)=O(n)方法四：遞推實(shí)現(xiàn)（消除數(shù)組）intF(intn){a=1,b=1,c=0；for(inti=3;i<=n;i++){c=a+b;a=b;b=c;}returnc;}第i次計(jì)算abc第i+1次計(jì)算abc斐波那契數(shù)列的時空復(fù)雜度分析實(shí)現(xiàn)：方法一

方法二方法三

方法四

時間復(fù)雜度：O(2n)O(n)O(n)空間復(fù)雜度：O(1)O(n)O(1)O(n)O(n)

（遞歸）

（備忘錄）

（遞推）

（空間優(yōu)化的遞推）從兔子繁殖問題引出斐波那契數(shù)列，并就該問題討論多種求解方法，每種方法的時空復(fù)雜度不同。問題分析：找規(guī)律很重要。問題求解：分析算法時空復(fù)雜度，不斷優(yōu)化。一個簡單但重要的思想：

避免重復(fù)計(jì)算的方法：保存結(jié)果（空間換時間）。信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—引例—數(shù)字三角形問題國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版數(shù)字三角形問題：求一自塔頂?shù)剿椎穆窂?，該路徑上結(jié)點(diǎn)值的和最大。138111015469522161417712規(guī)定：1.每一步可沿線向左下或右下走；2.1＜三角形高度≤100；3.三角形中的數(shù)字為整數(shù)，取值區(qū)間為[1,99]。1.窮舉法假定三角形高度為n，共2n-1條路徑，時間復(fù)雜度高達(dá)O(n2n-1)。1381110154695221614177122.貪心法：每次選值大的邊走。從上往下走：13+11+10+9+17=60，不是最優(yōu)解從下往上走：17+9+15+8+13=62，是最優(yōu)解，雖然該方法對于本實(shí)例可以得到正確解，但不適用于所有實(shí)例。138111015469522161417712試想一下，如果已經(jīng)得到了11和8到塔底的最優(yōu)路徑，那么13到塔底的最優(yōu)路徑是什么呢？13811101546952216141771213到塔底的最優(yōu)路徑=13+max(11和8到塔底的最優(yōu)路徑）變換：把左邊一列對齊，塔頂位于第1行第1列。結(jié)論：某個數(shù)到塔底的最優(yōu)路徑等于該數(shù)+max{其左下方的數(shù)到塔底的最優(yōu)路徑，其右下方的數(shù)到塔底的最優(yōu)路徑}138111015469522161417712令f(i,j)表示第i行第j列的數(shù)到塔底的最優(yōu)路徑值，則問題轉(zhuǎn)化為求f(1,1)。f(i,j)=?f(i,j)=a[i][j]，i=nf(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))

,

i<nf(i,j)表示第i行第j列的數(shù)到塔底的最優(yōu)路徑值。a[i,j]存儲第i行第j列中的數(shù);結(jié)論：某個數(shù)到塔底的最優(yōu)路徑等于該數(shù)+max{其左下方的數(shù)到塔底的最優(yōu)路徑，其右下方的數(shù)到塔底的最優(yōu)路徑}138111015469522161417712思考：上述遞歸代碼有什么缺點(diǎn)？遞歸實(shí)現(xiàn):inta[n+1][n+1];/*n表示總行數(shù)，a[i][j]是第i行第j列的值*/int

f(inti,intj)/*返回a[i][j]到塔底的最優(yōu)路徑上的結(jié)點(diǎn)和*/{if(i==n)returna[i][j];

returna[i][j]+max(f(i+1,j),f(i+1,j+1));}f(i,j)=a[i][j]，i=nf(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))

,

i<n方法一：遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)的缺點(diǎn)：遞歸深度大可能導(dǎo)致系統(tǒng)棧溢出。時間復(fù)雜度高。有很多子問題被重復(fù)計(jì)算！T(n)=2T(n-1)+O(1)=O(2n)f(i,j)=a[i][j]，i=nf(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))

,

i<n方法一：遞歸實(shí)現(xiàn)138111015469522161417712思考：如何解決上述問題？62494122164936261434127172238兩種實(shí)現(xiàn)方式：帶記憶的遞歸實(shí)現(xiàn)（備忘錄）自底向上的非遞歸實(shí)現(xiàn)1381110154695221614177121.inta[n+1][n+1];2.intf[n+1][n+1];/*f[i][j]初始為0*/3.int

Demo(inti,intj){4.if(i==n)f[i][j]=a[i][j];5.elseif(f[i][j]==0)6.f[i][j]=a[i][j]+max(Demo(i+1,j),Demo(i+1,j+1));7.returnf[i][j];8.}1.inta[n+1][n+1];2.intf[n+1][n+1];3.int

DP(){4.for(j=1;j<=n;j++) f[n][j]=a[n][j];5.for(i=n-1;i>=1;i--)6. for(j=1;j<=i;j++)7.f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);8.returnf[1][1];9.}方法二：帶記憶的遞歸實(shí)現(xiàn)（備忘錄）方法三：自底向上的非遞歸實(shí)現(xiàn)單選題。方法三（自底向上的非遞歸實(shí)現(xiàn)）求解數(shù)字三角形問題的時間復(fù)雜度是多少？A.O(n)B.O(n2)C.O(2n)D.O(1)問題1：如何得到最優(yōu)解？138111015469522161417712問題2：

如果只要求求解最優(yōu)值，空間可以優(yōu)化嗎？提示：使用一維數(shù)組，從左到右依次計(jì)算。138111015469522161417712問題和子問題具有最優(yōu)值遞歸關(guān)系遞歸實(shí)現(xiàn)時間復(fù)雜度O(n2n-1)自底向上的非遞歸現(xiàn)時間復(fù)雜度O(n2)帶記憶的遞歸現(xiàn)時間復(fù)雜度O(n2)窮舉法貪心法數(shù)字三角形問題復(fù)雜度高可能得不到最優(yōu)解信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—思想和步驟國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版兔子繁殖和數(shù)字三角形問題的共性：最優(yōu)化問題：在某些約束條件下，決定某些可選擇的變量應(yīng)該取何值，使所選定的目標(biāo)函數(shù)達(dá)到最優(yōu)的問題。問題與子問題有一定關(guān)系子問題需要多次使用：先求解子問題，并保存解，需要時直接讀取，以避免子問題重復(fù)計(jì)算基本思想兩個重要性質(zhì)解題步驟一二三

動態(tài)規(guī)劃與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，通過對子問題的求解得到原問題的解。T(n/m)T(n/m)T(n/m)T(n/m)……T(n)…………………………bdecfa子問題不是互相獨(dú)立適合使用動態(tài)規(guī)劃LRLRLRLRLRLRLR子問題互相獨(dú)立適合使用分治例：數(shù)字三角形問題例：歸并排序1.最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解包含子問題的最優(yōu)解。證明：通常用反證法

首先，假設(shè)問題最優(yōu)解A包含的子問題的解B不是最優(yōu)的，B’是子問題的最優(yōu)解；其次，說明在假設(shè)下可構(gòu)造出比原問題最優(yōu)解A更好的解A’，從而導(dǎo)致矛盾。ABA’B’剪切-粘貼法2.重疊子問題：有很多子問題會重復(fù)使用。動態(tài)規(guī)劃對每個子問題只求解一次，并將結(jié)果保存在表格中，當(dāng)需要再次使用時，用常數(shù)時間查表即可。找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。1和2是核心：確定問題和子問題的關(guān)系；3是實(shí)現(xiàn)方式：備忘錄或者自底向上；4是可選步驟：求最優(yōu)解時需要。動態(tài)規(guī)劃和分治的區(qū)別：子問題是否獨(dú)立。最優(yōu)子結(jié)構(gòu)和重疊子問題：使用動態(tài)規(guī)劃的條件。動態(tài)規(guī)劃的解題步驟：理清解題思路。信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—0-1背包問題之問題描述和分析國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版0-1背包問題：給定n個物品和一個背包。第i件物品的重量為wi，價值為vi，背包的容量為c。問應(yīng)選擇哪些物品裝入背包，使得背包中物品的總價值最大？限制條件：對每個物品只有兩種選擇，裝入或不裝入，物品不能分割。

與最大價值有關(guān)的因素背包容量和物品每個物品有兩種方案選或不選窮舉法共2n種方案

可以用動態(tài)規(guī)劃求解嗎？是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)背包容量c=7重量價值w1=3v1=5w2=4v2=6w3=5v3=10110最優(yōu)解是(1，1，0)，最大價值為11。問題：該問題的最優(yōu)解是否包含子問題的最優(yōu)解？問題：

背包容量c=7，物品總數(shù)n=3的0-1背包問題子問題：背包容量c或者物品總數(shù)n減少了的0-1背包問題問題：該問題的最優(yōu)解是否包含子問題的最優(yōu)解？子問題：c=3，n=2（1、3號物品）最優(yōu)解是(1，1，0)，最大價值為背包容量c=7重量價值w1=3v1=5w2=4v2=6w3=5v3=105背包容量c=310？剪切-粘貼法c=7，n=3，最優(yōu)解(1,1,0)最大價值為11c=3，n=2（1、3號物品）最優(yōu)解是(1,0)，最大價值=5c=3，n=2（1、3號物品）最優(yōu)解是(x1，x3)，最大價值>5c=7，n=3，最優(yōu)解(x1,1,x3)最大價值>11已知要證明假設(shè)得到比已知更好的最優(yōu)解，出現(xiàn)矛盾單選題。0-1背包問題：物品總數(shù)n=3，背包容量c=7，物品重量分別為(3,4,5)，價值分別為(5,6,10)，對應(yīng)的最優(yōu)解為（1,1,0），以下說法正確的是：A.(1,1)是前2個物品在背包容量為7時的最優(yōu)解。B.(1,0)不是后2個物品在背包容量為4時的最優(yōu)解。子問題：c=7，n=2最優(yōu)解是(1，1，0)背包容量c=7重量價值w1=3v1=5w2=4v2=6w3=5v3=1011

反證法：與已知矛盾，假設(shè)不成立

0-1背包問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)邏輯思維方法：從具體到一般從0-1背包問題的描述分析最優(yōu)子結(jié)構(gòu)，有一定難度?？山Y(jié)合具體實(shí)例，分析最優(yōu)子結(jié)構(gòu)涉及的幾個要素：問題、子問題、問題的最優(yōu)值、子問題的最優(yōu)值，把這些概念具體化后，再分析它們的關(guān)系，會容易一些。信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—0-1背包問題之動態(tài)規(guī)劃求解國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版動態(tài)規(guī)劃解題步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。定義：f(i,j)表示背包容量為j、可選物品編號為i,i+1,…,n時0-1背包問題的最優(yōu)值。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征f(i,j)表示背包容量為j、可選物品編號為i,i+1,…,n時0-1背包問題的最優(yōu)值。2.遞歸地定義最優(yōu)值nn-1i+1i……1

定義二維數(shù)組f[n+1][c+1]首列初始化000ed0ab000n1j-wici1

f(i,j)=max{vi

+f(i+1,j-wi),f(i+1,j)}i+1j3.以自底向上的方式計(jì)算最優(yōu)值自下而上、自左而右重疊子問題實(shí)例分析：初始化物品編號重量價值1212211033204215背包容量c=5，物品個數(shù)n=400000123452341ijc=5，n=4f數(shù)組實(shí)例分析：計(jì)算f(4,j)物品重量價值1212211033204215c=5，n=4000000123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(4,j)物品重量價值1212211033204215c=5，n=400000150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(4,j)物品重量價值1212211033204215c=5，n=400000151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(3,j)物品重量價值1212211033204215015202035c=5，n=400000151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(2,j)物品重量價值1212211033204215c=5，n=40010001520203500151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(2,j)物品重量價值1212211033204215c=5，n=4001015253035001520203500151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(1,j)物品重量價值1212211033204215c=5，n=40101525303701015253035001520203500151515150123452341ijf數(shù)組

打表法！算法描述Knapsack(n,c)1for

j

←0to

wn-1do

f[n,j]←0;2for

j

←

wn

to

c

do

f[n,j]←

vn;3for

i

←

n-1

to

1

do4for

j

←

0

to

c

do5if

wi>j

then6f[i,j]←

f[i+1,j];7else8f[i,j]←max{f[i+1,j],f[i+1,j-wi]+vi}時間復(fù)雜度T(n)=O(cn)方法：從問題最優(yōu)值開始倒推0000000:n1w-wici1i+1w五4.根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解

f(i,j)=max{vi

+f(i+1,j-wi),f(i+1,j)}0101525303701015253035000151515150123451234i015202035j實(shí)例分析：求最優(yōu)解物品重量價值1212211033204215信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—0-1背包問題之優(yōu)化和拓展國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版

動態(tài)規(guī)劃求解0-1背包問題時，空間復(fù)雜度為O(nc)。如果物品數(shù)n和背包容量c非常大時，算法對空間的需求也很大。

f(i,j)=max{vi

+f(i+1,j-wi),f(i+1,j)}000000000000000:n1w-wici0i+1w思考：是否可以對空間優(yōu)化？000:1w-wicf[0]f[1]w00f[0]f[1]以f[1]為基礎(chǔ)計(jì)算f[0]f[0]復(fù)制到f[1]中空間從f[n+1][c+1]

降低為f[2][c+1]。滾動數(shù)組f[k][j]=max{vi

+f[1-k][

j-wi],f[1-k][j]}k輪流取0,1000:1w-wicf[0]f[1]w空間從f[n+1][c+1]

降低為f[2][c+1]。進(jìn)一步，是否可以使用一維數(shù)組？00000000000d0ab00分析依賴關(guān)系，自右向左計(jì)算f[j]=max{vi

+f[j-wi],f[j]}單選題。如果使用一維數(shù)組的話，可以按照自左向右的順序計(jì)算0-1背包問題嗎？A.可以B.不可以單選題。對0-1背包問題進(jìn)行空間優(yōu)化后，還可以利用f數(shù)組求解最優(yōu)解嗎？A.能B.不能0-1背包代表了一類問題，具有以下特征：已知：n個可選擇的物品每個物品有若干屬性，比如重量和價值一個容器（背包），有一個屬性上的限制（容量）問題：在容器限制下，如何挑選物品（每個物品要么選要么不選）才能使得另一個屬性達(dá)到極大值？書名價格評級ACM知識與入門351算法競賽入門到進(jìn)階592ACM競賽題解793ACM算法基礎(chǔ)訓(xùn)練教程552ACM基本算法393算法競賽三部曲2402ACM高級教程1994挑戰(zhàn)程序設(shè)計(jì)競賽1633算法競賽寶典1325某同學(xué)為參加程序設(shè)計(jì)競賽準(zhǔn)備購買一批書籍，預(yù)算只有500元，他為不同書籍的重要性進(jìn)行了評級：1~5。問題：在預(yù)算有限的情況下，如何選擇才能使所買的所有書籍總的重要性最高？預(yù)算即背包容量書籍的價格即物品的重量書籍的重要性物品的價值集裝箱裝載特種兵背包物品的選擇滿背包問題選擇哪些物品剛好可以裝滿背包且價值最大完全背包問題每種物品有無限件多重背包問題第i種物品最多有Mi

件可用……理解和掌握典型應(yīng)用的主要特征，這樣才能在不同的應(yīng)用場景中，從現(xiàn)象到本質(zhì)，抓住關(guān)鍵點(diǎn)，活學(xué)活用。1.如果背包容量c和物品重量wi是小數(shù)，是否可以用動態(tài)規(guī)劃求解0-1背包問題？2.若c>2n，則動態(tài)規(guī)劃的時間復(fù)雜度為Ω(n2n)。與窮舉法相比如何？3.0-1背包問題中，f(i,j)表示背包容量為j、可選物品為i,i+1,…,n時問題的最優(yōu)值。類似地，你能想到其他的最優(yōu)值定義形式嗎?信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—矩陣連乘之問題描述和分析國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版矩陣連乘問題：給定n個矩陣{A1,A2,…,An}，其中Ai與Ai+1可乘，i=1，2…，n-1。確定一種計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的乘法次數(shù)最少。矩陣Ap*q

與矩陣Bq*j

相乘所需要的乘法次數(shù)為p*q*j。矩陣相乘的條件：矩陣A的列等于矩陣B的行。

X=共有5種計(jì)算方案：1.(A1(A2(A3A4)))：40*30*5+10*40*5+50*10*5=105002.(A1((A2A3)A4))：10*40*30+10*30*5+50*10*5=160003.((A1A2)(A3A4))：?4.((A1(A2A3))A4)：5.(((A1A2)A3)A4)：具體實(shí)例：4個矩陣相乘填空題。有A1=50*10，A2=10*40，A3=40*30，A4=30*5共4個矩陣，用((A1A2)(A3A4))這種計(jì)算次序?qū)?個矩陣相乘，需要的乘法次數(shù)為（）。共有5種計(jì)算方案：1.(A1(A2(A3A4)))：40*30*5+10*40*5+50*10*5=105002.(A1((A2A3)A4))：10*40*30+10*30*5+50*10*5=160003.((A1A2)(A3A4))：50*10*40+40*30*5+50*40*5=360004.((A1(A2A3))A4)：10*40*30+50*10*30+50*30*5=345005.(((A1A2)A3)A4)：50*10*40+50*40*30+50*30*5=87500具體實(shí)例：4個矩陣相乘1.窮舉法一共有多少種可能的計(jì)算次序？n個矩陣連乘問題，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題(A1...Ak)(Ak+1…An)，可以得到關(guān)于P(n)的遞推式如下：2.動態(tài)規(guī)劃是否滿足重疊子問題性質(zhì)？A1((A2A3)A4)、(A1(A2A3))A4是否滿足最優(yōu)子結(jié)構(gòu)性質(zhì)？(A1(A2(A3A4)))

(AiAi+1…Ak)(Ak+1Ak+2…Aj)

(AiAi+1…Ak)(Ak+1Ak+2…Aj)①②③④

計(jì)算左右兩個矩陣的乘法次數(shù)(AiAi+1…Ak)(Ak+1Ak+2…Aj)②③矩陣連乘問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—矩陣連乘之動態(tài)規(guī)劃求解國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版動態(tài)規(guī)劃解題步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。定義：m[i,j]表示AiAi+1…Aj矩陣連乘問題的最少乘法次數(shù)。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征

m[i,j]表示Ai…Aj矩陣連乘問題的最少乘法次數(shù)。2.遞歸地定義最優(yōu)值

3.以自底向上的方式計(jì)算最優(yōu)值1234…n1234…nm[i,j]表示Ai…Aj矩陣連乘問題的最少乘法次數(shù)。1個矩陣2個矩陣3個矩陣4個矩陣…n個矩陣123456123456m[i,j]A1A2252020

15A3A415

55

10A5A610

2020

30p0p1p2p3p4p5P625201551020301.初始化m[i,i]=0，i=1~62.計(jì)算相鄰2個矩陣m[1,2]=7500m[2,3]=1500m[3,4]=750m[4,5]=1000m[5,6]=6000p數(shù)組存放矩陣的行、列n=6個矩陣相乘07500000001500750100060001234561075002015003075040100050600060m[i,j]p0p1p2p3p4p5P62520155102030單選題。算一算，m[1,3]等于（）A.1500B.4000C.7500p數(shù)組存放矩陣的行、列12345610750040005250201500250045003075025006250401000400050600060m[i,j]p0p1p2p3p4p5P625201551020303.計(jì)算相鄰3個矩陣m[1,3],m[2,4],m[3,5],m[4,6]4.計(jì)算相鄰4個矩陣m[1,4],m[2,5],m[3,6]p數(shù)組存放矩陣的行、列p0p1p2p3p4p5P625201551020305.計(jì)算相鄰5個矩陣m[1,5]=7500m[2,6]=85006.計(jì)算相鄰6個矩陣m[1,6]=11750p數(shù)組存放矩陣的行、列123456107500400052507500117502015002500450085003075025006250401000400050600060m[i,j]for(intr=2;r<=n;r++)/*r表示長度*/

for(inti=1;i<=n-r+1;i++)/*i表示起點(diǎn)*/{intj=i+r-1;/*j表示終點(diǎn)*/for(intk=i;k<j;k++)/*k表示斷開位置*/

m[i][j]=min(m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];}123456123456求解矩陣連乘問題的代碼框架1.voidMatrixChain(int*p，intn，int**m，int**s)2.{3.for(inti=1;i<=n;i++)m[i][i]=0;4.for(intr=2;r<=n;r++){/*r是矩陣的數(shù)量*/5.for(inti=1;i<=n-r+1;i++)/*i是起始矩陣的編號*/6.{intj=i+r-1;/*j是終止矩陣的編號*/7.m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];8.s[i][j]=i;9.for(intk=i+1;k<j;k++){/*k是斷開的位置*/10.intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];11.if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}12.}13.}14.}空間復(fù)雜度：O(n2)時間復(fù)雜度：O(n3)123456123456123456123456單選題。矩陣連乘問題求解最優(yōu)值采用如圖(a)所示的計(jì)算次序，圖(b)給出了另一種計(jì)算次序，正確嗎？A.不正確B.正確(a)(b)123456101133320233330333404550560s[i,j]s[1,6]=3，得到(A1A2A3)(A4A5A6)s[1,3]=1，得到(A1(A2A3))s[4,6]=5，得到((A4A5)A6)最優(yōu)解為：((A1(A2A3))((A4A5)A6))4.根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解voidtraceback(int**s,inti,intj){if(i==j){printf(“A%d“,i);return;}intk=s[i][j];printf(“(“);traceback(s,i,k);traceback(s,k+1,j);printf(“)“);}4.根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解分析括號((A1(A2A3))

((A4A5)A6))每個問題（矩陣長度超過1）的解方案外有一對括號思考：是否可以進(jìn)行空間優(yōu)化？采用下標(biāo)轉(zhuǎn)換法，用一維數(shù)組代替二維數(shù)組，可以節(jié)省(N2-N)/2的空間。123456107500400052507500117502015002500450085003075025006250401000400050600060m[i,j]石子合并問題：

有n堆石子排成一排，依次編號為1~n?，F(xiàn)要將石子有次序地合并為一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為本次合并的得分。

試設(shè)計(jì)一算法，計(jì)算將n堆石子合并成一堆的最大得分。以n=4為例，每堆石子的個數(shù)為：3465，共5種合并方案。346510151810+15+18=43346511151811+15+18=4434657187+11+18=3611分析：每次只能選相鄰2堆石子合并，最后一次合并是左邊若干堆石子與右邊若干堆石子進(jìn)行合并，與矩陣連乘問題類似。sum(i,j)表示第i堆石子到第j堆石子的數(shù)量和，m(i,j)表示從第i堆石子到第j堆石子合并成一堆的最大得分，則有

共同特征往往可以將問題分解為兩兩合并的形式。其解決方法是對整個問題設(shè)最優(yōu)解，枚舉分割點(diǎn)，尋找最優(yōu)值。編程思路1.枚舉問題規(guī)模

2.枚舉起點(diǎn)，算出終點(diǎn)

3.枚舉分割點(diǎn)

4.利用最優(yōu)值遞歸關(guān)系計(jì)算信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—最長公共子序列之問題描述和分析國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版序列：由若干字符構(gòu)成的字符串或者文本。子序列：一個序列刪去若干元素后得到的序列。公共子序列：給定兩個序列X和Y，若序列Z既是X的子序列又是Y的子序列，稱Z是序列X和Y的公共子序列。最長公共子序列（LongestCommonSubsequence，LCS）：公共子序列中長度最長的子序列。例如:X=(B,D,A,B,A,C)

Y=(B,A,D,B,C,D,A)(B,D,

B,

A)公共子序列：(B,A,

B,

A)(B,A,

C)最長公共子序列最長公共子序列問題：給定兩個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的一個最長公共子序列。判斷：對于兩個序列X和Y，它們的最長公共子序列可能不唯一，但最長公共子序列的長度是唯一的。A.錯誤B.正確窮舉法：對于X的每一個子序列，驗(yàn)證它是否是Y的子序列。X有2m個子序列。每個子序列需要O(n)的時間來驗(yàn)證它是否是Y的子序列。時間復(fù)雜度:O(n2m)是否可以用動態(tài)規(guī)劃求解最長公共子序列問題呢？問題是否具有最優(yōu)子結(jié)構(gòu)和重疊子問題性質(zhì)？最優(yōu)子結(jié)構(gòu)性質(zhì)分析：問題的最優(yōu)值與兩個序列的長度有關(guān)。最長公共子序列(B,D,

B)?X=(B,D,A,B,A,C)

Y=(B,A,D,B,C,D,A)X’=(B,D,A,B)Y’=(B,A,D,B,C,D)最長公共子序列(B,D,

B,

A)問題子問題問題的最優(yōu)解包含子問題的最優(yōu)解序列Xm=(x1,x2,…,xm)，定義Xm的第i個前綴為：Xi=(x1,x2,…,xi)，i=0,1,2…m；最優(yōu)子結(jié)構(gòu)性質(zhì)：設(shè)序列Xm={x1,x2,…,xm}和Yn={y1,y2,…,yn}的一個最長公共子序列為Zk={z1,z2,…,zk}，則：若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列；若xm≠yn，且zk≠xm，則Zk是Xm-1和Yn的最長公共子序列；若xm≠yn，且zk≠yn，則Zk是Xm和Yn-1的最長公共子序列。信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—最長公共子序列之動態(tài)規(guī)劃求解國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版動態(tài)規(guī)劃解題步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。定義：c[i,j]為序列Xi=(x1,x2,…,xi)和Yj=(y1,y2,…,yj)的最長公共子序列的長度。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征c[i,j]為序列Xi=(x1,x2,…,xi)和Yj=(y1,y2,…,yj)的最長公共子序列的長度2.遞歸地定義最優(yōu)值

00000000000yjxmy1y2ynx1x2xi012nm120firstsecond

3.以自底向上的方式計(jì)算最優(yōu)值00000000000yjxmy1y2ynx1x2xi012nm120數(shù)組s[i,j]記錄最優(yōu)值對應(yīng)的信息如果xi=yj s[i,j]=1如果c[i-1,j]≥c[i,j-1]

s[i,j]=2否則 s[i,j]=3c[i,j-1]c[i-1,j]c[i-1,j-1]xiyj4.根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解實(shí)例分析：X=(B,D,A,B,A,C)Y=(B,A,D,B,C,D,A)0126345yjBADDBC51203467ABDxiABCA0000000

1

1

1

1

1

2

20000000

1

1

1

2

2

2

1

1

2

2

2

2

3

2

1

2

2

3

3

3

3

1

2

2

3

3

3

4

1

2

2

3

4

4

4如果xi=yj s[i,j]=“”如果c[i-1,j]≥c[i,j-1]

s[i,j]=“”否則 s[i,j]=“”實(shí)例分析：X=(B,D,A,B,A,C)Y=(B,A,D,B,C,D,A)0126345yjBADDBC51203467ABDxiABCA0000000

1

1

1

1

1

2

20000000

1

1

1

2

2

2

1

1

2

2

2

2

3

2

1

2

2

3

3

3

3

1

2

2

3

3

3

4

1

2

2

3

4

4

4得A得B得D得B最優(yōu)解：BDBAvoidLCSLength(intm，intn，char*x，char*y，int**c，int**s){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;s[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];s[i][j]=2;}else{c[i][j]=c[i][j-1];s[i][j]=3;}}}時間復(fù)雜度O(mn)/*構(gòu)造最優(yōu)解*/voidLCS(inti，intj，char*x，int**s){if(i==0||j==0)return;if(s[i][j]==1){LCS(i-1，j-1，x，s);cout<<x[i];}elseif(s[i][j]==2)LCS(i-1，j，x，s);elseLCS(i，j-1，x，s);}思考：以上計(jì)算過程可以優(yōu)化嗎？思考：數(shù)組s可以省去嗎？由于數(shù)組元素s[i][j]的值通過xi是否等于yj，c[i-1][j-1]，c[i-1][j]和c[i][j-1]確定，因此s數(shù)組可以省略。00000000000yjxmy1y2ynx1x2xi012nm120數(shù)組s[i,j]：記錄最優(yōu)解如果xi=yj s[i,j]=1如果c[i-1,j]≥c[i,j-1]

s[i,j]=2否則 s[i,j]=3c[i,j-1]c[i-1,j]c[i-1,j-1]xiyj思考：是否可以進(jìn)一步優(yōu)化空間？在計(jì)算c[i][j]時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間(滾動數(shù)組)就可以計(jì)算出最長公共子序列的長度。00000000000yjxmy1y2ynx1x2xi012nm120c[i,j-1]c[i-1,j]c[i-1,j-1]xiyj判斷：在求解X和Y的最長公共子序列時，X作為行或者列都是可以的。A.錯誤B.正確給定兩個單詞

word1

和

word2，找到使得

word1

和

word2

相同所需的最小步數(shù)，每步可以刪除任意一個字符串中的一個字符。

示例：輸入:"sea","eat“輸出:2解釋:第一步將"sea"變?yōu)?ea"，第二步將"eat"變?yōu)?ea"解題思路：求兩者的LCS=k，則最少步數(shù)=len(word1)+len(word2)-2k最長公共子序列反映了兩個序列的相似程度，廣泛應(yīng)用在許多領(lǐng)域：DNA序列比對論文相似性比對……信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—最長不上升子序列國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版某國為了防御敵國導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈的枚數(shù)和導(dǎo)彈依次飛來的高度，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈？樣例輸入：8389207155300

29917015865

樣例輸出：6最長不上升子序列問題最長不上升子序列問題：

設(shè)有一個正整數(shù)的序列a0,a1,…,an-1,對于下標(biāo)i1<i2<…＜im，若有ai1>=ai2>=…>=aim，則稱存在一個長度為m的不上升子序列。當(dāng)a0,a1,…,an-1給出之后，求最長不上升子序列的長度。i01234567a[i]38920715530029917015865問題分析：a[8]={389,207,155,300,299,170,158,65}i=0時，{389}，長度為1i=1時，{389207}，長度為2i=2時，{389207155}，長度為3i=3時，{389300}，長度為2……如果a[j]>=a[i]且j<i，那么以a[i]為結(jié)尾元素構(gòu)成的不上升子序列長度=以a[j]為結(jié)尾元素構(gòu)成的不上升子序列長度+1；a[i]為結(jié)尾元素構(gòu)成的最長不上升子序列長度=max{以a[j]為結(jié)尾元素構(gòu)成的最長不上升子序列長度+1}問題分析：定義f(i)表示以a[i]結(jié)尾的最長不上升子序列的長度。f(i)=max{f(j)+1}，且j<i，a[j]≥a[i]，0≤j<i<n。最長不上升子序列長度為max{f(i)}(0≤i≤n-1)。i01234567a[i]38920715530029917015865f[i]最優(yōu)值的計(jì)算過程：f(i)=max{f(j)+1}，且j<i，a[j]≥a[i]，0≤j<i<n。12323456整個問題的解為：max{f(i)}=6fori=0ton-1f[i]=1;/*初始化*/fori=1ton-1/*分階段求f[i]*/{maxlen=1;forj=0toi-1if(a[i]<=a[j]&&f[j]+1>maxlen)maxlen=f[j]+1;f[i]=maxlen;}maxlen=f[0];/*求最優(yōu)值*/fori=1ton-1iff[i]>maxlenmaxlen=f[i];printf(maxlen);時間復(fù)雜度T(n)=O(n2)思考：如何求解對應(yīng)的最優(yōu)解？設(shè)s(i)記錄f(i)對應(yīng)的j，即a[i]前面的一項(xiàng)為a[j]。從最大的f(i)開始，根據(jù)s(i)不斷得到其前面的若干項(xiàng)。最終得到38930029917015865i01234567a[i]38920715530029917015865f[i]12323456s[i]-10103456判斷題。一個序列的最長不上升子序列可能有多個。A.正確B.錯誤以下問題如何求解？最長上升子序列最長下降子序列最長不下降子序列信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—編輯距離問題國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版

設(shè)A和B是兩個字符串，要用最少的字符操作將A轉(zhuǎn)換為B。字符操作有三種：（1）刪除一個字符；（2）插入一個字符；（3）將一個字符改為另一個字符。

將字符串A轉(zhuǎn)換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離。字符串Abanana操作修改修改刪除字符串BpandaA轉(zhuǎn)換為B的編輯距離為3編輯距離反映兩個字符串的相似程度。最長公共子序列反映兩個字符串的相似程度。關(guān)注差異性bana

napanda編輯距離是3關(guān)注公共部分ba

nanapa

nda最長公共子序列是3字符串Abanana字符串Bpanda1.首先對比最后一個字符，都是a，相等；問題轉(zhuǎn)換為banan和pand的編輯距離問題；2.比較最后一個字符，n和d不等，取min{刪除n+bana和pand的編輯距離，插入d+banan和pan的編輯距離，修改n為d+bana和pan的編輯距離}3.…1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征

δ(A,B)表示字符串A和B的編輯距離。定義D[i,j]=δ(A[1..i],B[1..j])。D[i,j]=min{D[i-1,j-1]+δ(A[i],B[j]),D[i-1,j]+1,D[i,j-1]+1}；D[i,0]=i，i=0~m；D[0,j]=j，j=0~n；2.遞歸地定義最優(yōu)值3.以自底向上的方式計(jì)算最優(yōu)值00000000000BjAmB1B2BnA1A2Ai012nm1204.根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解定義C[i,j]：D[i,j]獲得最優(yōu)值時對應(yīng)的字符操作。C[i,j]=0：表示A[i]和B[j]相等C[i,j]=1：表示把A[i]修改為B[j]C[i,j]=2：表示刪除A[i]C[i,j]=3：表示插入B[j]實(shí)例分析：A=“banana”，B=“panda”

j=0j=1pj=2aj=3nj=4dj=5ai=0012345i=1b112345i=2a221234i=3n332123i=4a443222i=5n554333i=6a665443數(shù)組D[i,j]

j=0j=1pj=2aj=3nj=4dj=5ai=0033333i=1b21(修改)1111i=2a210(不變)330i=3n2120(不變)33i=4a2102(刪除)10i=5n21201(修改)1i=6a210210(不變)實(shí)例分析：A=”banana”，B=”panda”數(shù)組C[i,j]判斷題。編輯距離問題中，最優(yōu)解可能有多個。A.正確B.錯誤/*動態(tài)規(guī)劃求解編輯距離，字符串A長度為m，字符串B長度為n*/voideditDistance(char*A,char*B,intm,intn){……/*初始化D和C數(shù)組*/for(i=0;i<=m;i++){D[i][0]=i;C[i][0]=2;}for(j=0;j<=n;j++){D[0][j]=j;C[0][j]=3;}

for(i=1;i<=m;i++)for(j=1;j<=n;j++)/*當(dāng)字符相等時，不做任何操作*/

if(A[i]==B[j]){D[i][j]=D[i-1][j-1];C[i][j]=0;}else{t1=D[i-1][j-1]+1;t2=D[i-1][j]+1;t3=D[i][j-1]+1;if(t1<=t2&&t1<=t3){D[i][j]=t1;C[i][j]=1;}elseif(t2<=t1&&t2<=t3){D[i][j]=t2;C[i][j]=2;}

elseif(t3<=t1&&t3<=t2){D[i][j]=t3;C[i][j]=3;}}}時間復(fù)雜度：O(n2)空間復(fù)雜度：O(n2)

編輯距離反映了兩個字符串的相似程度，編輯距離越短，說明相似程度越高。

編輯距離問題通常用于需要對字符串進(jìn)行匹配的場景，包括DNA分析、拼寫檢查、語音識別等。信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—最優(yōu)二叉搜索樹國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版二叉搜索樹的定義：（1）是一棵二叉樹；（2）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（3）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（4）它的左、右子樹也分別為二叉搜索樹。4512533100在二叉搜索樹上查找不成功所需的比較次數(shù)是：虛擬結(jié)點(diǎn)的深度在二叉搜索樹上查找成功所需的比較次數(shù)是：結(jié)點(diǎn)的深度+1查找100的過程：與45比較；與53比較；與100比較；查找成功。查找40的過程：與45比較；與12比較；查找不成功。4553123100<33<x<1212<x<4545<x<53x>10053<x<100a1a2a3a4a5b0b1b2b3b4b5單選題。在下圖所示的二叉搜索樹上，查找90需要比較的次數(shù)是（）。A.3B.4C.24553123100<33<x<1212<x<4545<x<53x>10053<x<100a1a2a3a4a5b0b1b2b3b4b5

實(shí)例：假定S=<3,12,45,53,100>，P=<0.05,0.10,0.15,0.10,0.05,0.15,0.04,0.12,0.08,0.07,0.09>。(a)T=2.39(b)T=2.381.窮舉法有n個結(jié)點(diǎn)的二叉搜索樹的個數(shù)為P(n)，由于每個二叉搜索樹都可以分解為左子樹、根和右子樹，而左、右子樹都是二叉搜索樹，因此有：最優(yōu)二叉搜索樹滿足最優(yōu)子結(jié)構(gòu)性質(zhì)嗎？假設(shè)右圖是在給定序列S=<k1,k2,k3,k4,k5>,搜索概率為P=<q0,p1,q1,p2,q2,…,p5,q5>的最優(yōu)二叉搜索樹，那么其左子樹是以序列S1=<k1>及相應(yīng)概率對應(yīng)的最優(yōu)二叉搜索樹，其右子樹是以序列S2=<k3,k4,k5>及相應(yīng)概率對應(yīng)的最優(yōu)二叉搜索樹。反證法證明。定義S(i,j)=<ki,ki+1,…,kj

>概率分布P(i,j)=<qi-1,pi,qi,pi+1,…,pj，qj>w(i,j)=qi-1+pi+qi+pi+1+…+pj+qj

定義m(i,j)：

對應(yīng)S(i,j)和P(i,j)的最優(yōu)二叉搜索樹的平均比較次數(shù)。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征2.遞歸地定義最優(yōu)值3.以自底向上的方式計(jì)算最優(yōu)值123…n123…nm(i,j)1個結(jié)點(diǎn)2個結(jié)點(diǎn)3個結(jié)點(diǎn)…n個結(jié)點(diǎn)實(shí)例：S=<3,12,45,53,100>，P=<0.05,0.10,0.15,0.10,0.05,0.15,0.04,0.12,0.08,0.07,0.09>（1）首先計(jì)算1個結(jié)點(diǎn)的二叉搜索樹的平均比較次數(shù)m(1,1)、m(2,2)、m(3,3)、m(4,4)、m(5,5)。1253453100<33<x<1212<x<4545<x<53x>10053<x<100a2a1a3a4a5b0b1b2b3b4b53<x<12b112<x<45b245<x<5353<x<100b4b3m(1,1)m(2,2)m(3,3)m(4,4)m(5,5)（2）計(jì)算有2個結(jié)點(diǎn)的二叉搜索樹的最少平均比較次數(shù)m