给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1: 输入: 2 输出: [0,1,1] 示例 2: 输入: 5 输出: [0,1,1,2,1,2] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/counting-bits 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。题解
奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。 class Solution: def countBits(self, num: int) -> List[int]: dp = [0 for _ in range(num+1)] for i in range(1, num+1): if i & 1: dp[i] = dp[i-1] + 1 else: dp[i] = dp[i//2] return dp