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:
For num = 5 you should return [0,1,1,2,1,2].
最好把数字全都列出来然后找规律。
0 0000 0
-------------
1 0001 1
-------------
2 0010 1
3 0011 2
-------------
4 0100 1
5 0101 2
6 0110 2
7 0111 3
-------------
8 1000 1
9 1001 2
10 1010 2
11 1011 3
12 1100 2
13 1101 3
14 1110 3
15 1111 4
找规律就是递推，递推就是状态转移方程。这题的规律是f[i] = f[i / 2] + i % 2。
public int[] countBits(int num) {
int dp[] = new int[num + 1];
dp[0] = 0;
for (int i = 1; i <= num; i++) {
dp[i] = dp[i / 2] + i % 2;
}
return dp;
}
比较fancy的写法：
public int[] countBits(int num) {
int[] f = new int[num + 1];
for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
return f;
}
其他思路：
http://www.cnblogs.com/grandyang/p/5294255.html
