河北大学程序设计训练营

[TOC]

day24 兔子跳楼梯

小兔子喜欢蹦蹦跳跳上楼梯 ，它能一次跳1阶楼梯，也能一次跳上2阶楼梯。问小兔子要上一个n阶的楼梯，最多有多少种不同上楼的走法？

输入格式:

输入一行包含一个整数 n，表示有几阶楼梯。

输出格式:

上楼梯的走法数。

输入样例1:

3

输出样例1:

3

分析：

评测用例规模与约定
对于 20%的评测用例，1≤n≤10。 对于 50%的评测用例，1≤n≤100。 对于 80%的评测用例，1≤n≤1000。 对于所有评测用例，1≤n≤10000。

最简单的DP问题。我们知道，在这个上楼梯问题中，一次能上1阶或2阶楼梯。在到达第n(n>1)阶楼梯的时候，可以是从第n-1阶楼梯向上跳1阶楼梯，也可以是从n-2阶楼梯向上跳2阶楼梯。那么可以得出动规方程：a[n]=a[n-1]+a[n-2]。注意，当n<=1的时候要先处理，a[0]=a[1]=1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>

using namespace std;

int main()
{
int n;
int a[10010]={0};
int i;
    cin>>n;
    a[0]=a[1]=1;
    for(i=2;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
    cout<<a[n];
}