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