My idea is : (a bit complicated)

definition :

dp[x][0][0] = [...] , x   , x-1 , [...]
dp[x][0][0] = [...] , x-1 , x-1 , [...]
dp[x][1][0] = [...] , x   , x-1
dp[x][1][0] = [...] , x-1 , x
dp[x][1][0] = [...] , x-2 , x
(dp[x][i][j] is number of sequences satisfying the corresponding rule)

recurrence :

dp[i][0][0] = dp[i-1][0][1];
dp[i][0][1] = dp[i-1][0][0] + dp[i-1][1][0];
dp[i][1][0] = dp[i-1][1][1];
dp[i][1][1] = dp[i-1][1][1] + dp[i-1][1][2];
dp[i][1][2] = dp[i-1][1][0];

answer (to be printed is) :

dp[n][0][0] + dp[n][0][1] + dp[n][1][0] + dp[n][1][1] + dp[n][1][2]

proof :

left for you :)

Edited by author 02.05.2013 19:18

I have observed the answers.I found that a[i]=a[i-1]+a[i-2]-a[i-5];
I still don't know why!

Above has been shown:
a[i] = a[i-1] + a[i-3] + 1

this holds for each i, then also:
a[i-2] = a[i-3] + a[i-5] + 1

So
a[i-2] - a[i-3] - a[i-5] = 1

and (substitute this result in the first equation)
a[i] = a[i-1] + a[i-3] + a[i-2] - a[i-3] - a[i-5]

which reduces to
a[i] = a[i-1] + a[i-2] - a[i-5]

I use dfs to find the regular for some test
n  =   1 2 3 4 5 6 7   8    9    10   11
ans=   1 2 2 4 6 9 14  21   31   46   68
then I found f[n] = f[n-1] + f[n-2] - f[n-5]
then I got AC.

cool, note that we can unite 3rd and 4th cases as one case when n >= 4.