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