一、问题描述
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组ans 作为答案。
题目链接：比特位计数
二、题目要求
样例
输入：n=5输出： [0,1,1,2,1,2] 解释：0-->01-->12-->103-->114-->1005-->101
考察
动态规划中等题型，规律归纳有点难 建议用时15~30min
三、问题分析
对于这道题目，一开始，遇到这一题根本没想到用递归，因为脑子笨规律找不到。直接for循环一个个转换成2进制，对有1的数字进行计数，最后输出结果。
提交也成功通过了，只是有点耗费时空复杂度。
做出了就行，但我看了关于动态规划的题解，我沉默了，真TM的好！
接下来接着用我们的三步走，老套路了，开干：
第一步 含义搞懂：
题目要求求出二进制中1的个数，那么dp[i]就代表i转换成二进制之后，存储的数字。
第二步 变量初始：
这一题只需要初始一个变量，那就是dp[0]=0
第三步 规律归纳：
0-->01-->12-->13-->24-->15-->26-->27-->38-->19-->210-->2
我把前十个数字分成奇数、偶数分别列出来，看看有什么区别：
如果i是偶数，dp[i]=dp[i/2]; 因为是2进制，偶数除以一个2，也没有多出来一个1。 如果i是奇数，dp[i]=dp[i/2]+1;奇数就是比偶数多出来一个1
三步走，打完收工！
四、编码实现
classSolution { public: vector<int>countBits(intn) { longlonginti,k;//初始化变量vector<int>dp(n+1);//定义数组dp[0]=0;//第二步 变量初始for(i=1;i<=n;i++) { if(i%2==0)//第三步 规律归纳dp[i]=dp[i/2]; elsedp[i]=dp[i/2]+1; } returndp;//输出结果 } };
五、测试结果
好家伙，执行用时直接少了2/3
