AcWing 3643. 上楼梯

一个楼梯共有 n 级台阶，每次可以走一级或者两级或者三级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。

输入格式

一个整数 N。

输出格式

一个整数，表示方案总数。

数据范围

1≤N≤20

输入样例：

4

输出样例：

7

#include 
using namespace std;
const int N=1e9+7;
int dfs(int a)
//不过是多了一个选择 做法还是一样的 递归 
{
	if(a==1) return 1;
	if(a==2) return 2;
	if(a==3) return 4;
	return dfs(a-3)+dfs(a-2)+dfs(a-1);
}
#define int long long
signed main()
{
	int n;
	cin>>n;
	cout<<dfs(n)<<endl;
	return 0;
}