题目

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

测试样例：

输入: 2
输出: [0,1,1]

输入: 5
输出: [0,1,1,2,1,2]

思路

根据前两天的做题经验，拿到题目后先思考相邻数字之间是否存在一定的关系，这个关系不会太复杂，如果太复杂就要换个思路

这道题可以联想到2到3需要在0到1的二进制表示前补上1，4到7需要在0到3的二进制表示前面补上1，8到15需要在0到7的二进制表示前面补上1

也就是某个数字n，他的二进制表示就是n 减去 小于等于n的 最大的2的x次方 所得到的数字的二进制表示再在最高位补上一个1

代码

 1 class Solution {
 2 public:
 3     vector<int> countBits(int num) {
 4         vector<int> dp;
 5         dp.push_back(0);//数字0对应0个1
 6         int x=0;//2的x次方
 7         for(int i=1;i<=num;i++)
 8         {
 9             dp.push_back(dp[i-pow(2,x)]+1);
10             if(i+1>=pow(2,x+1))
11             {
12                 x++;
13             }
14         }
15         return dp;
16     }
17 };

反思

本题在做的时候不太容易想到dp关系，之前做的题都是相邻的项有一定的关系，这道题相邻的没有太大关系，而是距离一定距离的才有关系。以后再遇到类似的题的时候要联想到这种跳跃性的dp关系

另外如何想到要运用dp算法也是一个很值得思考的问题，下面贴上一篇博客，对于如何拿到一道题后是否要使用dp算法的思考有很大的帮助

https://www.cnblogs.com/y-knightqin/p/11681642.html

dp练习第三天-Leetcode338. 比特位计数

原文：https://www.cnblogs.com/wangqianming12138/p/14365916.html