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