算法合集之動(dòng)態(tài)規(guī)劃算法時(shí)間效率的優(yōu)化-在線(xiàn)瀏覽
2024-12-03 20:30本頁(yè)面
【正文】 m[i,i]=0 令 s[i,j]=k， 表示合并的最優(yōu)斷開(kāi)位置 。 設(shè)各堆的石子數(shù)依次為 d[1..n]， 則動(dòng)態(tài)規(guī)劃的狀態(tài)表示為： m[i,j]， 1≤i, j≤n， 表示合并 d[i..j]所得到的最大得分： 令 ， 則狀態(tài)轉(zhuǎn)移方程為： 合并第 i堆到第 j堆石子的最優(yōu)斷開(kāi)位置 s[i,j]要么等于 i， 要么等于 j1，也就是說(shuō)最優(yōu)合并方案只可能是： { (i) (i+1… j) } 或 { (i… j1) (j) } 證明：設(shè)合并第 i堆到第 j堆石子的最優(yōu)斷開(kāi)位置 s[i,j]=p， 且 ipj1。 于是最優(yōu)合并方案為： { [ (i… q) (q+1...p) ] (p+1… j) } 它的得分 F1=m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+t[i, p] 我們可以構(gòu)造如下的合并方案： { (i… q) [ (q+1...p) (p+1… j) ] } 它的得分 F2=m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+t[q+1,j] 由于 qp， 所以 t[i, p]≤t[p+1,j]t[q+1,j] 所以 F1F2， 這與合并第 i堆到第 j堆石子的最優(yōu)斷開(kāi)位置 s[i, j]=p矛盾 情況 t[i, p]t[p+1,j] 與情況 1是對(duì)稱(chēng)的 。 Back 例三 、 LOSTCI
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1