问题描述
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.
思路
动态规划
每个数字的1的个数，等于其right shift一位的那个数字的1的个数 ➕本身的末位是不是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
