POJ MT2144. 上楼梯

您所在的位置:网站首页 喜欢蹦蹦跳跳的小朋友怎么回事 POJ MT2144. 上楼梯

POJ MT2144. 上楼梯

2024-07-15 21:02| 来源: 网络整理| 查看: 265

题目描述

小码哥是个调皮的孩子,他上楼梯喜欢蹦蹦跳跳,也就是说,每次他会随机向上走1级或2级台阶。无聊的你想知道他从地面上到n层有多少中走法。每层楼之间有m级台阶。

格式

输入格式: 输入两个正整数m,n,代表每层台阶数以及要去到的楼层

输出格式: 输出一个数,代表所有可能的走法的总数。

样例

输入:

1 4

输出

3 思想

两个走楼梯的这个状态表示的解释很让我头疼,并且所求也是 如果走到第1级的走法是f[1]的话,可是现在就在第一级,那不就是f[0]=1??? 如果是向上走1级的走法是f[1],那么答案就应该是少走一级,毕竟现在在第1级台阶 1. 状态表示f[i],表示向上走到第i级台阶的走法 2. 集合划分:走到第i级台阶,走了1级台阶;走了2级台阶 3. 求的是数量,需要初始化,f[1]=1,f[2]=2是一定的 4. 根据状态转移方程就是斐波那契数列

注意 因为斐波那契数列后面很大, 考虑long long 如果选择f[i]为走到第i层楼层,解释起来就很难解释,不如就换种想法 n层楼层,实际上只上了n-1层。即使它说的是地面,地面就是第一层(结合实际思考) C++ 代码 #include using namespace std; const int N = 100; long long f[N]; int main( ) { int n,m; cin >> m >> n; f[1] = 1,f[2] = 2; int step = (n-1)*m; for(int i = 3;i


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3