レーザースタイル

タイトルの説明
x星の盛大な祝日は雰囲気を高めるために、30台の机光器で一列に並び、宇宙に光柱を打ち出す.デバッグをインストールしたところ、なぜか隣接する2台のレーザが同時に開かないことがわかりました!王は、このようなバグが存在する場合、全部で何種類のレーザー効果を出すことができるか知りたいと思っています.明らかに、3台の機械しかなければ、全部で5つのスタイルになることができます.つまり、すべて閉めて(sorry、この時は声がなくて、これも1つです)1台を開けて、3種類で2台を開けて、1種類30台だけではよくありません.王はあなたに手伝ってもらうしかありません.30台のレーザで形成できるパターン種数を表す整数を提出する必要がある.
コード1
暴力的な列挙は、バイナリで30個のランプを点灯させるため、0~2の30回-1の回数を列挙し、隣接する2つの1の場合を除去するだけである.

#include
using namespace std;
int get(int x,int k)// x  k    1
{
	return x>>k&1;
}
int main()
{
	int cnt=0;
	for(int i=0;i<1<<30;i++)
	{
		bool flag=true;
		for(int j=1;j<30;j++)
		{
			if(get(i,j)&&get(i,j-1))
			{
				flag=false;
				break;
			}
		}
		cnt+=flag;
	}
	cout<<cnt<<endl;
}

コード2
動的に計画する.x番目のビットが1の配列を1つの2次元配列f[x][1]で表す.f[x][0]はx位が0の配列を示し、f[x][1]の前面は0のみであるため、状態遷移方程式はf[x][1]=f[x-1][0]、f[x][0]の前面は0でも1でもある可能性があるため、f[x][0]=f[x-1][0]+f[x-1][1]となる.

#include
using namespace std;
int f[40][2];
int main()
{
	f[0][0]=1;
	for(int i=1;i<=30;i++)
	{
		f[i][0]=f[i-1][0]+f[i-1][1];
		f[i][1]=f[i-1][0];
	}
	cout<<f[30][0]+f[30][1];
}