洛谷 P10250 [GESP样题 六级] 下楼梯-普及-

题目描述

顽皮的小明发现，下楼梯时每步可以走 $1$ 个台阶、$2$ 个台阶或 $3$ 个台阶。现在一共有 $N$ 个台阶，你能帮小明算算有多少种方案吗？

输入格式

输入一行，包含一个整数 $N$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

4

输出 #1

7

输入输出样例 #2

输入 #2

10

输出 #2

274

说明/提示

对全部的测试点，保证 $1\le N\le 60$。

solution

简单的递推即可

代码

#include \"iostream\"#include \"cstddef\"#include \"vector\"#include \"unordered_map\"#include \"unordered_set\"#include \"queue\"#include \"stack\"#include \"algorithm\"#include \"sstream\"#include \"format\"#include \"cstdio\"#include \"cstring\"#include \"random\"#include \"ctime\"#include \"cstdlib\"#include \"algorithm\"using namespace std;const int N = 61;long long f[N];int main() { f[0] = 1; f[1] = 1; f[2] = 2; int n; cin >> n; for (int i = 3; i <= n; i++) { f[i] = f[i - 1] + f[i - 2] + f[i - 3]; } cout << f[n];}

结果