概念
動態規劃法離不開一個關鍵詞，拆分 ，就是把求解的問題分解成若干個子階段，前一問題的結果就是求解后一問題的子結構，在求解任一子問題時，列出各種可能的區域解，通過決策保留那些有可能達到最優的區域解，丟棄其他區域解，依次解決各子問題，最后一個子問題就是初始問題的解，
適用性
適用動態規劃的問題必須滿足最優化原理和無后效性，
最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略，簡而言之，一個最優化策略的子策略總是最優的，一個問題滿足最優化原理又稱其具有最優子結構性質，
將各階段按照一定的次序排列好之后，對于某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態，換句話說，每個狀態都是過去歷史的一個完整總結，這就是無后向性，又稱為無后效性，
解題思路
1.確定最優子結構:比如我們要求的結果F(X)的最優子結構可能為F(X-1)和F(X-2）
2.列轉移方程:根據最優子結構可以列出轉移方程F(X)=F(X-1)+F(X-2)
3.確定邊界值:確定問題的邊界，即當F(n)有可以確定的具體的值
以上概述是純粹是為了顯得官方一點，下面我們開始說人話
開始說人話
動態規劃法，規劃的意思就是劃分，求解一個問題時，把問題劃分成多個子階段，比如兔子繁殖問題，
有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問第n個月的兔子總數為多少？
對于這個問題，我們可以根據月份把問題劃分為n個階段，每個月的兔子數，都會等于前一個月的兔子數加上這個月新出生的兔子數，
所以 第n個月的兔子數=第n-1個月的兔子數+新出生的兔子數，
而 新出生的兔子數=有繁殖能力的兔子數=兩個月前的兔子數，
即：第n個月的兔子數=第n-1個月的兔子數+第n-2個月的兔子數
所以我們可以知道，我們要求的問題F(n)的最優子結構就是F(n-1)和F(n-2） ------對應解題思路的確定最優子結構
接著我們可以列出求解的方程 F(n)=F(n-1)+F(n-2) ----------列轉移方程
對于方程F(n) = F(n-1)+F(n-2) 我們發現 F(n-1)和F(n-2)的結果也不知道，但是我們可以用同樣的計算方法去求，F(n-1)=F(n-2)+F(n-3)以此類推，但是F(n)的在當n等于多少的時候才有確定的值呢，F(1）=1，F(2) = 1，這兩個就是F(n)的邊界值； -------確定邊界值
然后我們很容易就能寫出代碼
int f(int n){
if(n==1||n==2){
return 1;
}
return f(n-1)+f(n-2);
}
這就是使用動態規劃法解題的基本思路
確定最優子結構——》列轉移方程——》確定邊界值
上樓梯問題
一個樓梯有 10 級臺階，從下往上走，每跨一步只能向上邁 1 級或者 2 級臺階，請問一共有多少種走法？
解題思路:
要想走到第 10 級臺階，要么是先走到第 9 級，然后再邁一步 1 級臺階上去，要么是先走到第 8 級，然后一次邁 2 級臺階上去，
這樣的話，走到 10 級臺階的走法數，就等于走到 9 級臺階的走法數，加上走到 8 級臺階的走法數，
F(10) = F(9) + F(8) -------確定最優子結構
而且不光是 10 級臺階如此，走到任何一級臺階的走法數，都符合這個邏輯，因此就可以得出一個通用公式：
F(x) = F(x-1) + F(x-2) -------列轉移方程
其中上一級臺階的方式只有一種，而上兩級臺階的方式有兩種，得到F(1)=1,F(2)=2 -----找邊界值
代碼如下：
int F1(int n){
if(n==1){
return 1;
}
if(n==2){
return 2;
}
return F1(n-1)+F1(n-2);
}
但是很容易發現，這個代碼的時間復雜度是O（2^n)，當n的值較大的時候，計算的需要很長的時間
我們可以對代碼進行簡單的處理
int F2(int n){
if(n==1){
return 1;
}
if(n==2){
return 2;
}
int t1 = 1;
int t2 = 2;
int temp = 0;
for(int i=3;i<=n;i++){
temp = t1+t2;
t1 = t2;
t2 = temp;
}
return temp;
}
這樣時間復雜度就降低了很多
兔子問題
同理，兔子繁殖問題，我們也可以對代碼進行同樣的處理
void F(int n){
int[] i = new int[n];//兔子數
int[] s;//有生育能力的兔子數
i[0] = 1;
int t = 0;
for(int j = 0;j<n;j++){//j月份
if(j>=2){
t = i[j - 2];
}
if(j>=1){
i[j]=i[j-1]+t;
}
System.out.println("第"+(j+1)+"個月份的兔子數:"+i[j]);
}
}
01背包問題
01背包問題是動態規劃法的經典問題
? 有一個背包，可以裝載重量為5kg的物品，
? 有4個物品，他們的重量和價值如下，
? 背包：載重5kg
? 物品1
? 重量: 1kg
? 價值:￥3
? 物品2
? 重量:2kg
? 價值:￥4
? 物品3：
? 重量: 3kg
? 價值:￥5
? 物品4
? 重量:4kg
? 價值:￥6
? 那么請問，在不得超過背包的承重的情況下，將哪些物品放入背包，可以使得總價值最大?
總重量是5kg,從四個物品中選，我們要求的問題就是：F(5,4)，
對于第四個物品就只有兩種情況，我們可以選擇選，或者是不選
不選的話就還是5kg，只從前面三個物品去選，F(5,3)
選的話就是還剩下1kg，從前面三個去選，F(1,3)
F(5,4) = max { F(1,3) + 6, F(5,3) }
所以我們列出轉移方程：
F(W,N) =max { F(W-Wn, N-1) + Vn，F(W, N-1) } （w是重量，n是從前n個去選，Wn是第n個的重量，Vn是第n個的價值）
接下來就是找臨界值了：
當重量只剩下0kg的時候，就沒有能夠選擇的物品了，最大價值就是0，所以F(0,n)=0,
當只是剩下的重量大于0，但是已經遍歷到從前1個物品中選擇時，那么能選擇的物品就只有第一個，最大價值就是3，即F(n,1)=3
具體代碼如下：
static int F(int weight,int i,res[] resarr){//weight是重量，resarr保存的是物品重量和價值
if(weight==0){
return 0;
}
if(i==1){
return 3;
}
if(weight<resarr[i].getWeight()){//如果第i個物品的質量大于總的重量，則直接從前i-1個物品中去選擇
return F(weight,i-1,resarr);
}
return Math.max(F(weight-resarr[i].getWeight(),i-1,resarr)+resarr[i].getValue(),F(weight,i-1,resarr));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/273111.html
標籤：Java