递推经典例题 - 爬楼梯
一、题目阅读
题目描述
一段楼梯有n级台阶。你每次可以跨一个、两个或者三个台阶。
请问走上n级台阶有几种方案？答案对998244353取模。输入格式
一行一个数n。
输出格式
一行一个数，表示方案数。
样例
Input 1
3
Output 1
4
样例解释
1 + 1 + 1 = 3
1 + 2 = 3
2 + 1 = 3
3 = 3数据范围
n≤1000n≤1000
二、核心思路
走到第i级楼梯，可以从第i-1级楼梯、第i-2级楼梯、i-3级楼梯走来。
得出公式：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
三、题解
#include <bits/stdc++.h> using namespace std; int n, a[1005] = {0, 1, 2, 4}; int main() { cin >> n; for (int i = 4; i <= n; i++) a[i] = ((a[i - 1] + a[i - 2]) % 998244353 + a[i - 3]) % 998244353; cout << a[n] << endl; return 0; }
题目来自xinyoudui.com。