插空法，然后全加起来，不知道有没有更方便的方法

斐波拉契数列

直接手撸前4想
f(1)=2 {1,0}
f(2)=3 {11,01, 10}
f(3) =5 {111,011, 101,110,010}
f(3) =8 {1111,0111, 1011,1101,0101,1110,0110,1010}
f(n) = f(n-1) +f(n-2)
直接就是斐波拉契数列了

这题我的想法首先就觉得不是斐波那契那玩意通项太复杂，但是实践结果似乎反而还证实了。假设有i个0，n-i个1。0不相邻，因此取i-1个1将0隔开。剩余，剩下n-2i+1个相同的1，放入i+1个不同的箱子中，为组合数C(n-i+1, i)种(如果楼主不知道插板法求“球放箱”问题可以再问，或问老师)，把可能的0个数情况加起来即答案。写程序验证，确实是斐波那契(至于怎么理论推我也不会，高考不考，上大学也忘了很多)