問題描述

　　所謂的臺階問題就是說，從0開始上臺階1，2，3...n，每次只能上1個或者2個臺階。問上到n個臺階有多少種走法。這個問題是比較典型的，也有很多種變形，我們先講解下這種的實現。

?

問題分析

　　我們先按照舉例來分析，我測試了下，6個臺階時候的變化，如下個表　

臺階數	走法數
1	1
2	2
3	3
4	5
5	8
6	13

這特別像是一個斐波那契數列，那我們想下，如果有10階臺階，那么我們往后倒推，10階臺階肯定是第九個臺階和是第八個臺階上來的，那第九個臺階肯定是第八個臺階和第七個臺階上來的，第八個臺階肯定是第七個臺階和第六個臺階上來的，同理，我們得出了f(n)=f(n-1)+f(n-2)??

代碼實現

?

/*** 動態規劃算法，f(n)=f(n-1)+f(n-2)* @param n* @return*/private int getSolution(int n){if(n < 0){return -1;}if(n == 0){return 0;}if(n == 1){return 1;}int a = 1;int b = 1;int fn = 0;for(int i = 2; i < n+1; i++){fn = a + b;b = a;a = fn;}return fn;}

?

?

問題延伸

　　如果臺階問題變化一下，如果臺階隨意可以上，可以上1個，2個，3個.....n個，那么n個臺階的話，有多種走法呢？

　　我們來分析一波，按照上面說的，10個臺階，可以由第九個，八個，七個.......一個臺階都可以上來，那么第九個臺階可以由第八個，七個，六個.....一個臺階都可以上來，同理我們得出，

　　f(n)=f(n-1)+f(n-2)+.......+f(4)+f(3)+f(2)+f(1)

　　f(n-1) = f(n-2) +f(n-3) +........+f(4)+f(3)+f(2)+f(1)

　　經過上面兩個算式，我們可以得出，f(n)=2f(n-1)

?　代碼實現

1 /** 2 * 動態規劃算法， 3 * f(n)=2f(n-1) 4 * @param n 5 * @return 6 */ 7 private int getDoubleTree(int n){ 8 if(n < 0){ 9 return -1; 10 } 11 if(n==0){ 12 return 0; 13 } 14 if(n==1){ 15 return 0; 16 } 17 int a = 1; 18 int fn = 0; 19 for(int i = 2; i < n + 1; i++){ 20 fn = 2*a; 21 a = fn; 22 } 23 return fn; 24 }

?

?

?

?

　　

轉載于:https://www.cnblogs.com/lixiaochao/p/10025839.html

總結

以上是生活随笔為你收集整理的台阶问题---动态规划算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。