蓝桥杯 瓷砖铺放

瓷砖铺放  (vip)

 

问题描述

　　有一长度为 N(1<= Ｎ <=10) 的地板，给定两种不同瓷砖：一种长度为 1 ，另一种长度为 2 ，数目不限。要将这个长度为 N 的地板铺满，一共有多少种不同的铺法？

　　例如，长度为 4 的地面一共有如下 5 种铺法：

4=1+1+1+1

4=2+1+1

4=1+2+1

4=1+1+2

4=2+2

　　编程用递归的方法求解上述问题。

 

输入格式

　　只有一个数 N ，代表地板的长度

输出格式

　　输出一个数，代表所有不同的瓷砖铺放方法的总数

 

样例输入

4

样例输出

5

#include"iostream"
using namespace std;
int dfs(int x)
{
	if(x<0) return 0;
	if(x==0) return 1;
	return dfs(x-1)+dfs(x-2);
}
int main()
{
	int n;
	cin>>n;
	cout<<dfs(n);
	return 0;
}