上台阶
题目描述
有一楼梯共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
",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)
能力一般~~请多包涵~
希望对大家有帮助！