链接：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; } }转载于:https://www.cnblogs.com/Dup4/p/9433218.html
相关资源：JAVA上百实例源码以及开源项目