luogu-P10250题解

主要题意

一共有 $n$ 级台阶，每次可以下 $1$ , $2$ 或 $3$ 级台阶，请问一共有多少种方案。

解题思路

根据规律发现：

$n=1$ ： $1$ 种方案。
$n=2$ ： $2$ 种方案。
$n=3$ ： $4$ 种方案。
$n=4$ ： $7$ 种方案。
$n=5$ ： $13$ 种方案。
…… 可以发现，每一级台阶的走法都是上面 $3$ 级台阶走法的总和。

上代码！

#include<bits/stdc++.h>
using namespace std;
long long n,a[10001];
int main()
{ 
	a[0]=1,a[1]=2,a[2]=4;
    cin>>n;
    for(int i=3;i<n;i++)
		a[i]=a[i-1]+a[i-2]+a[i-3];
	cout<<a[n-1];
}