题目:

思路：

一旦看出来这是个状压dp就很好做了..某一行状态就只跟上一行有关.这样直接就转成线性dp了.

可是我没看出来.傻子吧啦.

 发现一个新的想法：O(n) 算出 1 ~ n 内所有数二进制数中1的个数.

AC代码: