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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20116
Problem 116 「赤タイル, 緑タイル, あるいは青タイル」 †

解法
左端から右端まで積めて言った場合を考えたら一瞬で解けますね。
計算量BigO(150)

#include <iostream>
using namespace std;

const int LIMIT=50;
long long int f(int size){
	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>size-1){
 				dp1[i]=dp0[i-(size-1)];
		}
	}
	return dp0[LIMIT]+dp1[LIMIT]-1;
}



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