问题：
求0～num
每个数的二进制中含有 1 的个数。
Example 1: Input: num = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Example 2: Input: num = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101 Constraints: 0 <= num <= 10^5 Follow up: It is very easy to come up with a solution with run time O(32n). Can you do it in linear time O(n) and possibly in a single pass? Could you solve it in O(n) space complexity? Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
解法：DP
1.状态：dp[n]：数字n的二进制有多少个 1。
2.选择：dp[n]=
3.base：
代码参考：
1 class Solution { 2 public: 3 //2 parts: 4 //last digit: odd:+1, even:+0 5 //other digit = Count(remove last digit: i>>1) 6 vector<int> countBits(int num) { 7 //int pow2 = 2; 8 int k=0, j=1; 9 vector<int> dp(num+1,0); 10 for(int i=1; i<=num; i++) { 11 dp[i]=dp[i>>1]; 12 if(i%2) dp[i]+=1; 13 } 14 return dp; 15 } 16 };
原文：https://www.cnblogs.com/habibah-chang/p/14628086.html