Leetcode Problem 338: Counting B

求从0-num的所有整数在二进制表示中的1的数目。

这个显然用动态规划来解。每一个整数，假设是32位的，其二进制1的数目，等于其左边31位中的1的数目，加上最后1位中1的数目。我们从小到大来计算，任何一个整数，其左边31位所代表的整数，一定在之前的运算中计算过了，因此查表即可。

• 空间复杂度：O(n)

• 时间复杂度：O(n)

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> results;
        results.push_back(0);
        
        for (int i = 1; i <= num; i++)
        {
            int a = i >> 1;
            int b = i & 1;
            results.push_back(results[a] + b);
        }
        
        return results;
    }
};