Need help in this DP question

chess
dynamic-programming
sequence

#1

Hi Everyone,
I was trying to solve an SOPJ DP problem. I can’t think of how to generalize this problem for each value of n.
Please someone have a look and let me know how to tackle this problem.
link text
thanks in advance.


#2

After getting some help and googling it , it seems clear to me that it basically counting number of ways to arrange numbers from 1 to n , with no consecutive numbers adjacent to each other. It can be solved using dp with bit masking
http://codeforces.com/blog/entry/16099 .
But because of very large value of n , I can’t decide how to determine the state of dp .Can anyone plz help me for any further pointers ?