問題描述

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.

思路

動態(tài)規(guī)劃
每個(gè)數(shù)字的1的個(gè)數(shù)，等于其right shift一位的那個(gè)數(shù)字的1的個(gè)數(shù) ?本身的末位是不是1

    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        ans = [0] * (num+1)
        for i in range (1, num+1):
            ans[i] = ans[i //2 ] + (i%2)
        return ans