算法設(shè)計(jì)與分析-第三章-動(dòng)態(tài)規(guī)劃-文庫(kù)吧資料
2024-08-17 10:38本頁(yè)面
【正文】 ?????2n ????????nn 動(dòng)態(tài)規(guī)劃法的基本步驟 ? 例 2 求解二項(xiàng)式系數(shù) 1 動(dòng)態(tài)規(guī)劃法： ????????0n????????1n????????2n????????3n????????4n????????5n????????6n ????????7nPascal 三角形 n 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 7 1 7 21 35 35 21 7 1 動(dòng)態(tài)規(guī)劃法的基本步驟 ? 例 2 求解二項(xiàng)式系數(shù) int Binom（ int n, int m） { int b[MAXSIZE]。 } return f。 f1=f。 i=n。 動(dòng)態(tài)規(guī)劃法的基本步驟 int Fib(int n) { f1=f2=0。 ? 以自底向上迭代的方式（或以自頂向下的 備忘錄方法 ）計(jì)算出 最優(yōu)值 ； ? 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造 最優(yōu)解 。－－考察是否適合采用動(dòng)態(tài)規(guī)劃法。 這種性質(zhì)稱為 子問題的重疊性質(zhì) 。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。 所以，最短路徑問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。接下去，問題就轉(zhuǎn)化為用 i1替代 i，重復(fù)原來的問題，找出一條從 i1到 j的路徑。 下面證明最短路徑問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 動(dòng)態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) ?證明： ? 設(shè) i,i1,i2,…,i k,j是從 i到 j的一條最短路徑。 例 2：求解二項(xiàng)式系數(shù) )!(!!mnmnmn??????????????????mn??????????????????? ?111mnmn1 1 m=0 n=m 其它 ＝ 動(dòng)態(tài)規(guī)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1