河北大学程序设计训练营
[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。
c++
1 |
|