小时候我们都玩过爬楼梯的游戏:两人猜拳,赢了可向上爬一级,谁先到最高级则获胜。作为大学生,我们应该玩一个更有水平的游戏。
现在一个人要上n级楼梯,每一步可以选择上一级或者上两级,但是不能后退。求上这n级楼梯的方案数。
Input
第一行只有一个整数T(1<=T<=45),表示数据组数。
下面的T行每一行有一个整数n(1<=n<=45),表示有多少级楼梯。
Output
对于每一组数据输出一个整数s,表示方案数。
Sample Input
41234
Sample Output
1235 简单的斐波那契数列形式递推,状态转移方程为f[i] = f[i-1] + f[i-2]
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int main(){ 8 int t, n; 9 cin >> t;10 int a[46];11 a[1] = 1;a[2] = 2;12 for(int i = 3;i <= 45;i++)13 a[i] = a[i-1] + a[i-2];14 while(t--){15 cin >> n;16 cout << a[n] << endl;17 }18 return 0;19 }