ブルーブリッジカップVIP試験問題アルゴリズム訓練タイル舗装

試験問題アルゴリズム訓練タイル舗装
リソース制限時間制限:1.0 sメモリ制限:512.0 MBの問題では、長さN(1<=N<=10)の床が記述されており、2つの異なるタイルが与えられています.1つは長さ1で、もう1つは長さ2で、数は制限されません.この長さNの床を敷き詰めるには、全部で何種類の異なる敷き方がありますか?例えば,長さが4の地面には,4=1+1+1+14=2+1+14=1+2+14=1+1+2 4=2+2プログラミングが再帰的な方法で上記の問題を解く5つの舗装法がある.入力フォーマットは1つの数Nのみで、床の長さ出力フォーマットを表して1つの数を出力し、すべての異なるタイル舗装方法の総数サンプル入力4サンプル出力5を表します.
構想:最初は再帰的、遡及的に検出したいと思っていたが、1=1種2=1+1、2=2種3=1+1、3=1+2、3=2+1種4=1+1+1、4=1+1+2、4=1+2+1、4=2+2+1、4=2+2 5種5=1+1+1+1、5=1+1+2、5=2+1+1+1、5=2+1+1、5=2+1+1、5=2+2+2、5=2+2+2、5=2+2+1フィボナッチ数列と同様にNが2より大きい場合、前の2項の和は第3項に等しく、1と2の個数を見てもよく、すべて1またはすべて2の場合は1種であり、1の数が2より大きい場合は1,2の数が1より大きい場合は2,3の1の2の変動2の位置が1の個数に1を加え、2の2の1の場合は1の変動1の位置が2の個数に1を加え、偶数がすべて2で奇数が1つしかない場合に終わりますが、前にフィボナッチ数列を使う方法は簡単です.
コードは次のとおりです.

#include
using namespace std;
int sum=0,n;
int dgs(int n){
	if(n==1){
		return sum++;
	}else if(n==2){
		return sum+=2;
	}else{
		return dgs(n-1)+dgs(n-2);
	}
}
int main(){
	cin>>n;
	dgs(n);
	cout<<sum;
}