题目链接：338
思路
本题最重要的是找到奇偶数之间比特1的数量关系。
0=00，1=01，2=10，3=11
有以下规律：
- 如果 i 是奇数，则 bit1Num(i) == bit1Num(i-1) + 1
- 如果 i 是偶数，则 bit1Num(i) == bit1Num(i / 2)
- bit1Num(0) = 0
对于第一条规律，由于一个奇数和更小的相邻的偶数相比，就是在最低位多了一个1，因此1的总个数也多1。
对于第二条规律，一个偶数可以看作是另一个数左移一位得到的，因此该偶数和左移前的数的1的个数是相同的，左移前的数即为 i / 2。
有了以上三条，可以写出动态规划：
// if i is odd, then countOne(i) == countOne(i - 1) + 1
// if i is even, then countOne(i) == countOne(i / 2)
// when i == 0, countOne(i) == 0
func countBits(num int) []int {
ans := make([]int, num + 1)
// Base case
ans[0] = 0
for i := 1; i <= num; i++ {
// use '&' to define odd or even
if i & 1 == 1 {
// odd
ans[i] = ans[i - 1] + 1
} else {
// even
ans[i] = ans[i / 2]
}
}
return ans
}
时间复杂度：O(n)
空间复杂度：O(1)
