超级阶梯(一步两步)

杭电 2041

题目链接:acm.hdu.edu.cn/showproblem.php?pid=2041

题目描述:

题目

解题思路:

每次只能走一步或者两步,所以从第三级阶梯开始,到达当前阶梯i可以从i-1,i-2阶梯到达,所以到达当前阶梯i的方案数目为i-1阶梯,i-2阶梯方案数目之和。dp[i]=dp[i-1]+dpi-2

代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
int dp[maxn];
int main(){
    scanf("%d",&n);
    while(n--){
        memset(dp,0,sizeof(dp));
        scanf("%d",&m);
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=m;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        printf("%d\n",dp[m]);
    }
    return 0;
} 
Last modification:December 7th, 2019 at 06:02 pm
如果觉得我的文章对你有用,请随意赞赏