Counting Bits

给一个数n, 返回一个数组里面是, 1到n所有1的bits的计数. 这个用dp做, dp[i] 就是i的bit.

class Solution {
    public int[] countBits(int num) {
        int result = 0;
        int j = 1;
        int dp[] = new int[num+1];
        // for 0, it is 0
        dp[0] = 0;
        if(num == 0){
            return dp;
        }
        // for 1, it is 1
        dp[1] = 1;
        if(num == 1){
            return dp;
        }
        
        // for all power of 2, it is 1. for exmple 4 is 100 in binary
        for(int i=2;i<=num;i=i*2){
            dp[i] = 1;            
        }
        
        // for rest of number, 
        for(int i=2;i<=num;i++){
            if(dp[i] == 1){
                j = i;
            }else{ // if dp[i] == 0, then the number of 1 bit of i is equals to the previous number of 1 + number of 1 bit of dp[i-j]'s 
                dp[i] = dp[j] + dp[i-j]; 
            }  
        }
        return dp;
    }
}