POJ MT2144. 上楼梯 |
您所在的位置:网站首页 › 喜欢蹦蹦跳跳的小朋友怎么回事 › POJ MT2144. 上楼梯 |
题目描述
小码哥是个调皮的孩子,他上楼梯喜欢蹦蹦跳跳,也就是说,每次他会随机向上走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 |