Need help in this DP question



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.


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 .
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 ?