338. Counting Bits

问题

输出一个数组，元素为[0, num]中每个数的二进制数中1的个数。

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

思路

对于二进制以0结尾的（能被2整除）数，加1后1的个数加1。比如111比110多一个1。对于二进制以1结尾的数，加1后变成以0结尾的数，此时1的个数会等于这个数的1/2的1的个数。比如110和11的1的个数相同。

i能被2整除时：(dp[i] = dp[i-1] +1)。
否则：(dp[i] = dp[i/2])。

时间复杂度O(n)，空间复杂度O(n)

代码

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        lis = [0] * (num+1)
        for i in range(1,num+1):
            if(i % 2 == 1):
                lis[i] = lis[i-1] + 1
            else:
                lis[i] = lis[i/2]
        return lis