UVa 11069 A Graph Problem

題意：

1. 子集合內數字不能相鄰
2. 要盡可能填滿，比如n=6，那麼就不能有{3,6}而是要{1,3,6}，不能是{1,4}而是要{1,4,6}

想法：

　　一開始很直覺的使用遞迴一直往下尋找，但是使用遞迴會TLE，換個想法，很類似高中排列組合的階梯問題，本題是一次走2階或3階：

• n=1{1} : 1
• n=2{1,2} : 2
• n=3{1,2,3} : 2
• 當n=4{1,2,3,4}，有哪些情況會選到'4'? n=1({1,4})或n=2({2,4})的情況，所以n(4)=n(1)+n(2)=3
• 當n=5{1,2,3,4,5}，會選到'5'的情況有n=2({2,5})或n=3({1,3,5})，所以n(5)=n(2)+n(3)=4
• 以此類推..