动态规划例题（二）

一、leetcode地址

leetcode地址：https://leetcode-cn.com/problems/counting-bits/

二、题目比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。例如：
输入: 2
输出: [0,1,1]

三、解法

先分析，然后找规律，最后求解。

1、统计法

直接利用求二进制的函数，进行统计“1”的数量统计即可

class Solution:
    def countBits(self, num: int) -> List[int]:
        res=[]
        for i in range(num+1):
            res.append(bin(i).count('1'))
        return res

2、递归

在做这一题的时候，二进制之间的规律并不清楚，我就在本子上从0开始写，然后规律就出现了

十进制数字	转为二进制	‘1’的个数
0	0	0
1	1	1
2	10	1
3	11	2
4	100	1
5	101	2
6	110	2
7	111	3
8	1000	1
9	1001	2
...	...	...

我们可以得到的信息是：
1、偶数的二进制末尾为0，奇数的二进制末尾为1，所以第一n个数是奇数的情况下，第n个数字的二进制中的‘1’的个数一定比第(n-1)个数字二进制中的‘1’的个数多1个。
2、当第n个数字为偶数时，第n个数字的二进制数右移一位就是第n/2的二进制数（这个是二进制的位运算），因为偶数二进制末尾为‘0’，故‘1’的个数不变。
递归的代码如下：

class Solution:
    def countBits(self, num: int) -> List[int]:
        res=[]
        for i in range(num+1):
            res.append(self.count(i))
        return res

    def count(self,num):
        if num==0:
            return 0
        if num % 2==1:
            return self.count(num-1)+1
        return self.count(num//2)

3、动态规划

利用递归总结的规律，记录每一步的信息，直接调用值计算即可
代码如下：

class Solution:
    def countBits(self, num: int) -> List[int]:
        res=[0]*(num+1)
        for i in range(1,num+1):
            res[i]=res[i>>1]+(i&1)
        return res

小提示：‘i>>1’表示位运算右移一位，‘i&1’表示奇偶性，奇数值为1，偶数值为0