最近開始看算法導論，研究了一下動態(tài)規(guī)劃，下面就開始直入主題開始記錄近期看的第一個知識點動態(tài)規(guī)劃。提起動態(tài)規(guī)劃就不得不提幾個動態(tài)規(guī)劃的金典問題爬樓梯、國王金礦、背包問題。今天就仔細分析一下爬樓梯問題。

列子 問：有一個高度為10級臺階的樓梯，從下往上走，每一次向上跨一個臺階只能是一個臺階或者兩個臺階，要求用程序求出來一共有多少種算法？

思考：如果每次都跨一個臺階 則為 1+1+1+1+1+1+1+1+1+1這種方式 、如果每次都跨兩個臺階則為2+2+2+2+2+2......很多很多種,最簡單暴力的算法就是寫個多種循環(huán)遞歸調用輸出所有的可行的方法,但是這種方法時效率最低的時間復雜度成指數(shù)形式遞增。現(xiàn)在我們就開始考慮用動態(tài)規(guī)劃的思路來思考這個問題，動態(tài)規(guī)劃的思路就是將問題拆分、分治。

首先將問題先考慮爬樓梯的問題執(zhí)行到最后一步了，只差一步就可以結束這個請款下的問題，在這個時候只有兩種可能了一、從第9階樓梯跨一步到達10階和從第8階一次性跨兩個臺階到達10階。假設到達第9階臺階的方法為a種,到達第8階的方法為b種 則到達第10階的方法則為a+b，ok這個時候我們簡寫 到10階臺階的方法為F(10)，則F(10) = F(9)+F(8)，然后同理繼續(xù)拆分? ? ? ?F(9)=F(8)+F(7),F(8)=F(7)+F(6),拆分到最后當臺階只剩下1階和二階的時候很容易得到一個常量 F(1)=1,F(2)=2,由此可得一個公式：

F(n) = F(n-1)+F(n-2) (n>=3)

這個時候我們就得到了用到了動態(tài)規(guī)劃的的概念 F(9)和F(8)是F(10)的最優(yōu)子結構，F(1)=1,F(2)=2就是動態(tài)規(guī)劃所謂的問題的邊界，而上面所得到的公式就是狀態(tài)轉移方程，好了到現(xiàn)在為止 已近理清了我們的思路現(xiàn)在就要開始考慮如何解問題了，代碼采用java編寫

方法一、

public int getClimblingWays(intn){if ( n<1 ) return 0;if (n == 1)return 1;if (n == 2)return 2;return getClimblingWays(n-1)+getClimblingWays(n-2);

}

當然這個方法可以解決這個問題但是我們也要考慮 這個是不是運行了是很重復的計算，下面是一張所有計算節(jié)點的圖

這個算法的時間復雜度是一個是一個二叉樹，每一個節(jié)點都去過去進行計算即使已經(jīng)計算過了 ,我們可不可以做個緩存記住已近計算好的結果呢？這里我們就引出了第二種方法

方法二、備忘錄算法

public int getClimblingWaysWithCache(int n, Mapmap){if ( n<1 ) return 0;if (n == 1)return 1;if (n == 2)return 2;if(map.containsKey(n)){returnmap.get(n);

}else{int val = getClimblingWaysWithCache(n-1,map)+getClimblingWaysWithCache(n-2,map);

map.put(n,val);returnval;

}

}

這種算法大大減少時間復雜度，其時間復雜發(fā)度和空間復雜度都為O(n)

到這里為止我們并未結束 我們要開始轉為一下思維我們不用自頂向下的方法轉化為自底向上的方法，如圖所示：

在臺階大于3以后 每一個臺階的走法數(shù)之和前兩個臺階數(shù)有關所有我們在可以優(yōu)化一種新的方法并不不需要記住每一個子集的解，只需要記住前面兩個方法的解就好，因此我們引入了第三種方法

方法三、動態(tài)規(guī)劃解法

public int getClimblingWays3(intn ){if ( n<1 ) return 0;if (n == 1)return 1;if (n == 2)return 2;int a = 1;int b = 2;int temp =0;for(int i = 3;i <= n ;i++){

temp= b +a;

a=b;

b=temp;

}returntemp;

}

程序從i=3開始到i=n結束 即只有F(n)n>=3的時候才開始進入循環(huán)。好了到此為止最簡單的動態(tài)規(guī)劃問題就全部梳理好了。

總結

以上是生活随笔為你收集整理的java 爬楼梯算法_动态规划-爬楼梯问题java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。