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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20115
Problem 115 「ブロックの組み合わせ方の数え上げ その2」 †

解法
1+1は2風味な漸化式で片が付きます。
計算量はBigO(N),ループ一重で片が付く。

#include<stdio.h>
#include<vector>

const int LIMIT=50;
int main(){
	std::vector<int> dp;
	int addA=0;
	int addB=0;
 	int sumA=0;
	int sumB=0;
	for(int i=0;i<=LIMIT;i++){
		dp.push_back(0);
	}
	for(int i=LIMIT;;i++){
 		addA++;
		sumA+=addA;
		if(i>=LIMIT+1){
			sumB+=addB+dp[i-LIMIT-1];
		addB+=dp[i-LIMIT-1];
 		}
		dp[i]=sumA+sumB;
		dp.push_back(0);
 		if(dp[i]+1>1000*1000){
			printf("%d\n",i);
			break;
		}
	}
}