動(dòng)態(tài)規(guī)劃的重要性就不多說(shuō),直接進(jìn)入正題
首先,我們看一下官方定義:
定義:
動(dòng)態(tài)規(guī)劃算法是通過(guò)拆分問(wèn)題，定義問(wèn)題狀態(tài)和狀態(tài)之間的關(guān)系，使得問(wèn)題能夠以遞推（或者說(shuō)分治）的方式去解決。
動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類(lèi)似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。
基本思想與策略編輯:
由于動(dòng)態(tài)規(guī)劃解決的問(wèn)題多數(shù)有重疊子問(wèn)題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對(duì)每一個(gè)子問(wèn)題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。
(來(lái)自百度百科)
說(shuō)實(shí)話(huà),沒(méi)有動(dòng)態(tài)規(guī)劃的基礎(chǔ)很難看懂,但是也能從中看出一些信息,下面我翻譯成人話(huà):
首先是拆分問(wèn)題,我的理解就是根據(jù)問(wèn)題的可能性把問(wèn)題劃分成一步一步這樣就可以通過(guò)遞推或者遞歸來(lái)實(shí)現(xiàn).
關(guān)鍵就是這個(gè)步驟,動(dòng)態(tài)規(guī)劃有一類(lèi)問(wèn)題就是從后往前推到,有時(shí)候我們很容易知道:如果只有一種情況時(shí),最佳的選擇應(yīng)該怎么做.然后根據(jù)這個(gè)最佳選擇往前一步推導(dǎo),得到前一步的最佳選擇
然后就是定義問(wèn)題狀態(tài)和狀態(tài)之間的關(guān)系,我的理解是前面拆分的步驟之間的關(guān)系,用一種量化的形式表現(xiàn)出來(lái),類(lèi)似于高中學(xué)的推導(dǎo)公式,因?yàn)檫@種式子很容易用程序?qū)懗鰜?lái),也可以說(shuō)對(duì)程序比較親和(也就是最后所說(shuō)的狀態(tài)轉(zhuǎn)移方程式)
我們?cè)賮?lái)看定義的下面的兩段,我的理解是比如我們找到最優(yōu)解,我們應(yīng)該講最優(yōu)解保存下來(lái),為了往前推導(dǎo)時(shí)能夠使用前一步的最優(yōu)解,在這個(gè)過(guò)程中難免有一些相比于最優(yōu)解差的解,此時(shí)我們應(yīng)該放棄,只保存最優(yōu)解,這樣我們每一次都把最優(yōu)解保存了下來(lái),大大降低了時(shí)間復(fù)雜度
說(shuō)很難理解清楚,容易懵懵懂懂的,所以下面結(jié)合實(shí)例看一下(建議結(jié)合實(shí)例,紙上談兵不太好):
經(jīng)典的數(shù)字三角形問(wèn)題(簡(jiǎn)單易懂,經(jīng)典動(dòng)態(tài)規(guī)劃);
可以看出每走第n行第m列時(shí)有兩種后續(xù):向下或者向右下
由于最后一行可以確定,當(dāng)做邊界條件,所以我們自然而然想到遞歸求解
解題思路:
下面簡(jiǎn)單寫(xiě)一下JAVA代碼:
//java代碼純屬自己練習(xí),標(biāo)準(zhǔn)答案參考上面的C語(yǔ)言答案
class solution{
public int getMax(){
int MAX = 101;
int[][] D = new int[MAX][MAX]; //存儲(chǔ)數(shù)字三角形
int n; //n表示層數(shù)
int i = 0; int j = 0;
int maxSum = getMaxSum(D,n,i,j);
return maxSum;
}
public int getMaxSum(int[][] D,int n,int i,int j){
if(i == n){
return D[i][j];
}
int x = getMaxSum(D,n,i+1,j);
int y = getMaxSum(D,n,i+1,j+1);
return Math.max(x,y)+D[i][j];
}
}
其實(shí)仔細(xì)觀察,上面的解答過(guò)程時(shí)間復(fù)雜度難以想象的大,那是因?yàn)樗麑?duì)有的數(shù)字的解進(jìn)行了多次的重復(fù)計(jì)算,具體如下圖:
如果不明白上圖,可以把每條路徑都畫(huà)出來(lái),觀察每個(gè)數(shù)字有多少條路徑經(jīng)過(guò)了他,就會(huì)一目了然
然后我們就可以自然而然的想到,如果我們每次都把結(jié)果保存下來(lái),復(fù)雜度就會(huì)大大降低
其實(shí)答案很簡(jiǎn)單:
其實(shí),仔細(xì)觀察該解題過(guò)程,該過(guò)程就是標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃解題過(guò)程,如果把該過(guò)程畫(huà)出來(lái)(找到每一步的最優(yōu)解,其他的舍棄)對(duì)動(dòng)態(tài)規(guī)劃會(huì)有更深刻的解法
還有就是,遞推的另一個(gè)好處是可以進(jìn)行空間優(yōu)化,如圖:
下面總結(jié)一下動(dòng)態(tài)規(guī)劃的解題一般思路:
首先遞歸應(yīng)該是我們解決動(dòng)態(tài)規(guī)劃問(wèn)題最常用的方法,帥,速度不算太慢
那么遞歸到動(dòng)規(guī)的一般轉(zhuǎn)化方法為:
如果該遞歸函數(shù)有n個(gè)參數(shù),那么就定義一個(gè)n維數(shù)組,數(shù)組下標(biāo)是遞歸函數(shù)參數(shù)的取值范圍(也就是數(shù)組每一維的大小).數(shù)組元素的值就是遞歸函數(shù)的返回值(初始化為一個(gè)標(biāo)志值,表明還未被填充),這樣就可以從邊界值開(kāi)始逐步的填充數(shù)組,相當(dāng)于計(jì)算遞歸函數(shù)的逆過(guò)程(這和前面所說(shuō)的推導(dǎo)過(guò)程應(yīng)該是相同的).
動(dòng)規(guī)解題的一般思路(標(biāo)準(zhǔn)官方,不過(guò)經(jīng)過(guò)前邊講解應(yīng)該就能理解了):
將原問(wèn)題分解為子問(wèn)題(開(kāi)頭已經(jīng)介紹了怎么分解)
(注意:1,子問(wèn)題與原問(wèn)題形式相同或類(lèi)似,只是問(wèn)題規(guī)模變小了,從而變簡(jiǎn)單了;
2,子問(wèn)題一旦求出就要保存下來(lái),保證每個(gè)子問(wèn)題只求解一遍)
確定狀態(tài)(狀態(tài):在動(dòng)規(guī)解題中,我們將和子問(wèn)題相關(guān)的各個(gè)變量的一組取值,稱(chēng)之為一個(gè)"狀態(tài)",一個(gè)狀態(tài)對(duì)應(yīng)一個(gè)或多個(gè)子問(wèn)題所謂的在某個(gè)狀態(tài)的值,這個(gè)就是狀態(tài)所對(duì)應(yīng)的子問(wèn)題的解,所有狀態(tài)的集合稱(chēng)為"狀態(tài)空間".我的理解就是狀態(tài)就是某個(gè)問(wèn)題某組變量,狀態(tài)空間就是該問(wèn)題的所有組變量) 另外:整個(gè)問(wèn)題的時(shí)間復(fù)雜度就是狀態(tài)數(shù)目乘以每個(gè)狀態(tài)所需要的時(shí)間
確定一些初始狀態(tài)(邊界條件)的值 (這個(gè)視情況而定,千萬(wàn)別以為就是最簡(jiǎn)單的那個(gè)子問(wèn)題解,上面只是例子,真正實(shí)踐動(dòng)規(guī)千變?nèi)f化)
確定狀態(tài)轉(zhuǎn)移方程 (這一步和第三步是最關(guān)鍵的 記住"人人為我"遞推,由已知推未知)
適合使用動(dòng)規(guī)求解的問(wèn)題:
1,問(wèn)題具有最優(yōu)子結(jié)構(gòu)
2,無(wú)后效性 說(shuō)的花里胡哨的,其實(shí)一般遇到求最優(yōu)解問(wèn)題一般適合使用動(dòng)態(tài)規(guī)劃
