Namomo Spring Camp Div2 Week1 - 第二次打卡

楼梯有 n 阶，上楼可以一步上一阶，也可以一步上二阶。

但你不能连续三步都走两阶，计算走到第n阶共有多少种不同的走法。

输入格式

一行，一个数字，表示n。

输出格式

输出走楼梯的方式总数。

样例输入

6

样例输出

12

数据规模

对于100%的数据，保证n≤50。

第一种方法，DFS+打表

DFS在n = 40左右时速度明显下降，所以我们可以把 n=40~50的ans打表

AC代码如下：

#include
#include
#include
#include
#include
#include 
#include
#include 
using namespace std;
typedef long long  ll;
const int inf = 0x3f3f3f3f;
#define fo(x) for(int i = 1;i<=x;++i)
#define ios ios::sync_with_stdio(false);cin.tie(0), cout.tie(0)
const int N = 1e6+9;
ll ans = 0;
int n;
void dfs(int x,int flag)
{
	if(x==n)
	{
		ans ++;
		return ; 
	}
	if(x>n)	return ;
	if(flag != 2)
	{
		dfs(x+1,0);
		dfs(x+2,flag+1);
	}
	else
	{
		dfs(x+1,0);
	}
}
int main()
{
	ios;
	cin>>n;
	if(n<40)
	{
		dfs(0,0);
		cout<

第二种方法（正解）DP

水题，一看代码就明白了，就不多解释了（：

AC代码如下：

#include
#include
#include
#include
#include
#include 
#include
#include 
using namespace std;
typedef long long  ll;
const int inf = 0x3f3f3f3f;
#define fo(x) for(int i = 1;i<=x;++i)
#define ios ios::sync_with_stdio(false);cin.tie(0), cout.tie(0)
const int N = 1e6+9;
ll dp[55][5];
int main()
{
	ios;
	int n;
	cin>>n;
	dp[1][0] = 1;
	dp[1][1] = 0;
	dp[1][2] = 0;
	dp[2][0] = 1;
	dp[2][1] = 1;
	dp[2][2] = 0;
	for(int i = 3;i<=n;i++)
	{
		dp[i][0] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
		dp[i][1] = dp[i-2][0];
		dp[i][2] = dp[i-2][1];
	}
	cout<