算法設計與分析 課件 5.2-動態(tài)規(guī)劃引例2-數(shù)字三角形問題

信息工程大學算法設計與分析動態(tài)規(guī)劃—引例—數(shù)字三角形問題國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版數(shù)字三角形問題：求一自塔頂?shù)剿椎穆窂剑撀窂缴辖Y(jié)點值的和最大。138111015469522161417712規(guī)定：1.每一步可沿線向左下或右下走；2.1＜三角形高度≤100；3.三角形中的數(shù)字為整數(shù)，取值區(qū)間為[1,99]。1.窮舉法假定三角形高度為n，共2n-1條路徑，時間復雜度高達O(n2n-1)。1381110154695221614177122.貪心法：每次選值大的邊走。從上往下走：13+11+10+9+17=60，不是最優(yōu)解從下往上走：17+9+15+8+13=62，是最優(yōu)解，雖然該方法對于本實例可以得到正確解，但不適用于所有實例。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思考：上述遞歸代碼有什么缺點？遞歸實現(xiàn):inta[n+1][n+1];/*n表示總行數(shù)，a[i][j]是第i行第j列的值*/int

f(inti,intj)/*返回a[i][j]到塔底的最優(yōu)路徑上的結(jié)點和*/{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方法一：遞歸實現(xiàn)遞歸實現(xiàn)的缺點：遞歸深度大可能導致系統(tǒng)棧溢出。時間復雜度高。有很多子問題被重復計算！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方法一：遞歸實現(xiàn)138111015469522161417712思考：如何解決上述問題？62494122164936261434127172238兩種實現(xiàn)方式：帶記憶的遞歸實現(xiàn)（備忘錄）自底向上的非遞歸實現(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.}方法二：帶記憶的遞歸實現(xiàn)（備忘錄）方法三：自底向上的非遞歸實現(xiàn)單選題。方法三（自底向上的非遞歸實現(xiàn)）求解數(shù)字三角形問題的時間復雜度是多少？A.O(n)B.O(n2)C.O(2n)D.O(1)問題1：如何得到最優(yōu)解？138111015469522161417712問題2：

如果只要求求解最優(yōu)值，空間可以優(yōu)化嗎？提示：使用一維數(shù)組，從左到右依次計算。138111015469522161