DP的算法就不说了，记一种打表找规律法（大草）。
通过打表，我们发现答案如下：
2 1
3-4 2 1
5-8 2 2 3 1
9-16 2 2 3 2 3 3 4 1
17-32 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1
33-64 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1
可以很容易发现规律：
2 1
3-4 2 1
5-8 2 2 3 1
9-16 2 2 3 2 3 3 4 1
17-32 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1
33-64 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1
即图中深蓝数段就是浅蓝段整体+1。这样我们可以猜测出65-128的结果：
65-128 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7
经过对拍，和暴力程序给出的答案完全一致，因此可以认为这个规律是正确的。
代码：
class Solution { public: vector<int> countBits(int n){ vector<int> ans; ans.push_back(0); if (n==0) return ans; ans.push_back(1); if (n==1) return ans; ans.push_back(1); if (n==2) return ans; ans.push_back(2); if (n==3) return ans; ans.push_back(1); if (n==4) return ans; int t=8,tt; while (t<=n){ tt=t>>1; for (int i=(t>>2)+1;i<tt;i++) ans.push_back(ans[i]); ans.push_back(2); tt=(t>>1)+(t>>2); for (int i=(t>>1)+1;i<tt;i++) ans.push_back(ans[i]+1); ans.push_back(1); t<<=1; } if (n<(t>>1)+(t>>2)){ t=(t>>1)+1; int i=(t>>1)+1; while (t<=n){ ans.push_back(ans[i]); i++,t++; } } else if (n==(t>>1)+(t>>2)){ t=(t>>1)+1; int i=(t>>1)+1; while (t<n){ ans.push_back(ans[i]); i++,t++; } ans.push_back(2); } else{ tt=t-(t>>2),t=(t>>1)+1; int i=(t>>1)+1; while (t<tt){ ans.push_back(ans[i]); i++,t++; } ans.push_back(2); t=tt+1,i=(tt<<1)/3+1; while (t<=n){ ans.push_back(ans[i]+1); t++,i++; } } return ans; } };