10918

Using DP

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int f[35];
int g[35];

int main()
{
	for(int i=0;i<35;i++)
		f[i]=g[i]=0;
	f[0]=1;
	f[1]=0;
	g[0]=0;
	g[1]=1;//one missing cornered rect of size 3x1
	for(int i=2;i<35;i++)
	{
		f[i]=f[i-2]+2*g[i-1];//if last column are 3 of (2x1) OR one vertical 2x1(and removing that will leave one missing cornered ractngle of 2 ways)
		g[i]=f[i-1]+g[i-2];//one missing cornered rectangle can be 1.last one vertical 2x1 and 2. 2 horizontal 2x1 if we remove them wil form another missing cornered rectangle
	}
	int n;
	while(scanf("%d",&n) && n!=-1)
	{
		printf("%d\n",f[n]);
	}
	return 0;
}

Another way of adhoc suggested in a blog.

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int arr[35];

//lets assume if last column are all horizontal tiles of 3 *(2x1), so remove that and this 3*(2x1) can be
// tiled 3 ways ,so total ways for n length is ways[n-2]*3
//if n>=4 then for every term it can be shifted upside down adds two more ways
// so for n>=4
int main()
{
	for(int i=0;i<35;i++)
		arr[i]=0;
	arr[0]=1;

	for(int i=2;i<35;i+=2)
	{
		arr[i]+=3*arr[i-2];
		for(int j=4;j<=i;j+=2)
		{
			arr[i] += 2*arr[i-j];
		}
	}
	int n;
	while(scanf("%d",&n) && n!=-1)
	{
		printf("%d\n",arr[n]);
	}
	return 0;
}