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

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

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小明在坐景驰科技研发的无人车到达了目的地。
景驰科技（JingChi.ai）是一家由人工智能技术驱动、以无人驾驶技术为核心的智能出行公司。它将打造面向中国市场的全无人驾驶。
从无人车下来以后，小明看到了一个长长的楼梯。
有一个n级台阶的楼梯，小明一次可以向上跳1步，两步，甚至是n步，请问小明跳到n级台阶有多少种跳法？
输入描述:

第一行输入一个整数t，代表有t组样例:（ T<=30）
接下来的t行，都用一个整数n，表示楼梯有n级台阶（ 1<=n<=30）

输出描述:

输出跳到第n级台阶有多少种跳法

示例1
输入

1
1

输出

1

思路
其实就是 爬楼梯问题的升级版
我们来分析一下 爬楼梯问题
爬楼梯 问题 是 一次 可以跳一格，两格，或者三格
那么跳一格的情况 就是 dp[n - 1] 的所有情况
然后跳二格的情况 就是 dp[n - 2] 的所有情况
最后 跳三格的情况就是 dp[n - 3] 的所有情况

递推公式
dp[n] = dp[n - 1] + dp[n - 2] + … + dp[1]

AC代码

#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-3;

const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const int MOD = 1e9 + 7;

ll ans[31] = { 0 };

int main()
{
    for (int i = 1; i < 31; i++)
    {
        ans[i] = 1;
        for (int j = 0; j < i; j++)
            ans[i] += ans[j];
    }
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        cout << ans[n] << endl;
    }
}