上臺階
題目描述
有一樓梯共m級，剛開始時你在第一級，若每次只能跨上一級或二級，要走上第m級，共有多少走法？
注：規定從一級到一級有0種走法。
輸入
輸入數據首先包含一個整數n(1<=n<=100)，表示測試實例的個數，然后是n行數據，每行包含一個整數m，（1<=m<=40), 表示樓梯的級數。
樣例輸入
2
2
3
輸出
對于每個測試實例，請輸出不同走法的數量。
樣例輸出
1
2
時間限制
C/C++語言：2000MS其它語言：4000MS
內存限制
C/C++語言：65537KB其它語言：589825KB
在賽碼網做算法題，遇到這樣一個問題。
雖然我還很一般，還需要繼續進步，但是希望能夠記錄下學習的新知識。
把握自己的思想寫下來，提供給沒有想法的伙伴們一個參考~
代碼捉襟見肘，還請見諒~
這是一個動態規劃問題。
動態規劃的特點是，一個龐大的問題我們可以把它分成多個階段，每個階段得到一個結果作為下一個階段的開始。
但是每個階段都有多種可能性，每一種決策會影響當前的結果但是對下一階段是沒有影響的，階段之間相互獨立，只選擇決策自己。
下面說一下我的思路：
當前我們站在1臺階 輸入一個m 代表目標臺階
1 如果m是1 則 答案是0種
2 如果m是2 只有一種可能:1步上去 則答案是1種
3 如果m是3 兩種可能：兩次1步；一次2步 則答案是2種
4 如果m是4 有兩種情況到達4 從2邁2臺階到4； 從3邁1臺階到4， 從1到2有1種、1到3有2種，所以 我們把這兩種情況加在一起 1+2 答案是3種
5 如果m是5 有兩種情況到達4 從3邁2臺階到5； 從4邁1臺階到5； 從1到4有3種、1到3有2種 所以 我們把這兩種情況加在一起 3+2 答案是5種
......
之后都是一樣的，我們從一開始往后推算，任何一個臺階都可以從上一個臺階邁1臺階 或者 上兩個臺階 邁兩個臺階過來，從1臺階到 前一臺階或者前兩臺階都計算過。我們把兩種情況相加就是這個目標的答案。
這就是很典型的動態規劃算法的思想了：
請看代碼，
python3版本：
1 #coding:utf8
2 def count(steps):
3 if steps == 1:
4 return 0
5 if steps == 2:
6 return 1
7 if steps == 3:
8 return 2
9 return count(steps -1) + count(steps -2)
10 if __name__ == '__main__':
11 m = int(input())
12 for i in range(m):
13 n = int( input() )
14 print( count(n) ) ?
?
?
鑒于python的使用量還不夠龐大，我又用c寫了一遍相同的實現。
C語言版本： 1 int count( steps ){
2 if( steps == 1 ) return 0;
3 if( steps == 2 ) return 1;
4 if( steps == 3 ) return 2;
5 return count(steps -1 )+ count(steps -2);
6 }
7 int main(){
8 int n,m;
9 scanf("%d",&n);
10 while( n-- ){
11 scanf("%d",&m);
12 printf("%d\n",count(m));
13 }
14 return 0;
15 } ?
這兩種語言實現相同的思想。不用糾結哪種語言。
?
不過經歷了上面的分析，我們發現，每次臺階的結果都是前兩個臺階結果的加和！！
這不禁讓我們聯想到斐波那契數，斐波那契數就是 前兩項都是1，從第三項開始，每一項都是前兩項加和。
所以用生成斐波那契數的方法來實現：
python版本：
1 #斐波那契數列實現：
2 def getResult(n):
3 i = 2
4 num1 = 1
5 num2 = 1
6 while i <= n:
7 num1, num2 = num2, num1 + num2
8 i += 1
9 print(num1)
10 if __name__ == '__main__':
11 m = int(input())
12 for i in range(m):
13 n = int(input())
14 getResult(n) ?
能力一般~~請多包涵~
希望對大家有幫助！
![bzoj1016 [JSOI2008]最小生成樹計數](http://pic.xiahunao.cn/bzoj1016 [JSOI2008]最小生成樹計數)
)
