递推经典例题 - 爬楼梯

一、题目阅读

题目描述

一段楼梯有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。