【DP】338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2
Output: [0,1,1]

Example 2:

Input: 5
Output: [0,1,1,2,1,2]

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

解题思路：

Follow up 里面说了，很容易想出 O(n*sizeof(integer)) 的方法，即计算每一个数中 1 的个数。

如果要达到 O(n) 的复杂度，可以使用动态规划的思想。创建 dp[nums+1]，其中 dp[i] 表示数字 i 中 1 的个数，最后 dp 本身就是答案。

做法有很多，关键是通过观察规律，找到转移方程。这里介绍两种容易想到的 DP 方法：

方法1：

观察数字规律，比如 14（1110）可以通过 6（110）在前面加一个 1 得到；6（110）可以通过 2（10）在前面加一个 1 得到；2 （10）可以通过在 0（0）前面加 1 个 1 得到；再比如 13（1101）可以通过 5（101）在前面加一个 1 得到；5（101）可以通过 1 （01）在前面加一个 1 得到。其他数字规律也是一样。

因此，我们可以得到转移方程：dp[i] = dp[i-2**exp] + 1，其中，2**exp 是不超过数字 i 的 2 次幂。如 dp[14] = dp[14-2**3] + 1；dp[6] = dp[6-2**2] + 1；dp[2] = dp[2-2**1] + 1。

Python3 实现：

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

方法2：

观察数字规律，总结后可以得出递推公式，如下：

• f(n) = f(n/2) + 0，如果 n 为偶数
• f(n) = f(n/2) + 1，如果 n 为奇数

根据上面的递推公式就可以在 O(n) 时间内完成计算每个数位 1 的个数了。

Python3 实现：

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//2] + 1
            else:
                dp[i]  = dp[i//2]
        return dp