第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--A-跳台阶

链接：https://www.nowcoder.com/acm/contest/90/A
来源：牛客网

1.题目描述
小明在坐景驰科技研发的无人车到达了目的地。
景驰科技（JingChi.ai）是一家由人工智能技术驱动、以无人驾驶技术为核心的智能出行公司。它将打造面向中国市场的全无人驾驶。
从无人车下来以后，小明看到了一个长长的楼梯。
有一个n级台阶的楼梯，小明一次可以向上跳1步，两步，甚至是n步，请问小明跳到n级台阶有多少种跳法？
输入描述:
第一行输入一个整数t，代表有t组样例:（ T<=30）
接下来的t行，都用一个整数n，表示楼梯有n级台阶（ 1<=n<=30）
输出描述:
输出跳到第n级台阶有多少种跳法
示例1
输入
1
1
输出
1
2.题目分析
这种题目做过很多了，最简单就是递归实现了。比如：

int Jump(int n)

{

    if (n <= 0)  return 0;

    if (n == 1 || n == 2) return n;

    return (Jump(n-1) + Jump(n-2));

}

但是这是实际就是个斐波那契数列的计算，这么算太慢，改成非递归即可。

3.代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

#include<algorithm>

using namespace std;

typedef long long ll;

const double PI = acos(-1.0);

const double eps = 1e-6;

const int INF = 1000000000;

const int maxn = 100;

int Jump(int n)

{

    if (n <= 0)  return 0;

    if (n == 1 || n == 2) return n;

    return (Jump(n-1) + Jump(n-2));

}

int main()

{   ll dp[45],T,step;

    dp[1]=1;

    for(int i=2;i<40;i++)

    {   dp[i]=1;

        for(int j=i-1;j>=1;j--)

        dp[i]+=dp[j];

    }

    cin>>T;

    while(T--)

    {

        cin>>step;

        cout<<dp[step]<<endl;

    }

    return 0;

}

秒客网

第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--A-跳台阶

相关文章