Counting Bits

Counting Bits

典型的动态规划

/*  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;
    }