プロジェクトオイラー問117 - sinapusu2002 @ ウィキ

Problem 117 「赤タイル, 緑タイル, そして青タイル」 †
50マスに1、２，３、4の長さのタイルを隙間なく敷き詰める。
何通りの敷き詰め方があるか？

解法
フィボナッチ数列の発展で
BigO(150)
です。

#include <iostream>
using namespace std; 

const int LIMIT=50;
long long int f(){
	long long int dp0[LIMIT+1]={1,0},dp1[LIMIT+1]={0};
 	for(int i=1;i<=LIMIT;i++){
		dp0[i]=dp0[i-1]+dp1[i-1];
		if(i>1){
 			dp1[i]+=dp0[i-1];
		}
		if(i>2){
 			dp1[i]+=dp0[i-2];
		}
 		if(i>3){
			dp1[i]+=dp0[i-3];
		}
 	}
	return dp0[LIMIT]+dp1[LIMIT];
}



int main() {
	// your code goes here
	cout<<f();
	return 0;
}