典型的動態(tài)規(guī)劃
/* int[] res = new int[num +1];
for(int i = 1; i <= num; i++)
res[i] = res[i >>1] + (i&1);
return res;*/
public int[] countBits(int num) {
int baseNum = 0;
long low = (long) Math.pow(2, baseNum);
long top = (long) Math.pow(2, baseNum + 1);
int[] results = new int[num + 1];
results[0] = 0;
for (int i = 1; i <= num; i++) {
if (i == low) {
results[i] = 1;
} else if (i > low && i < top) {
results[i] = 1 + results[(int) (i - low)];
} else if (i == top) {
results[i] = 1;
baseNum++;
low = (long) Math.pow(2, baseNum);
top = (long) Math.pow(2, baseNum + 1);
}
}
return results;
}
