#338 Counting Bits

Concept: 0 1 2 3 4 5 6 7 8 9 10 11 0,1,1,2,1,2 2 3 1 2 2 3 每個數字都是前一個2的某次方的數字加上另一個數字， 例如 10 = 8 + 2，8和2分別有1個1，10就有2個1。 用一個dp[] 存每個數字有幾個1， 用一個int exp 存當前最大的2的次方數字， dp[i] = dp[exp] + dp[i-exp]

Code:

public class Solution {
    public int[] countBits(int num) {

        //handle base case
        int[] dp = new int[num+1];
        if(num == 0){
            dp[0] = 0;
            return dp;
        }
        if(num == 1){
            dp[0] = 0;
            dp[1] = 1;
            return dp;
        }
        //initialize dp
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        int exp = 2;
        for(int i = 3; i< num+1; i++){
            if(i / exp == 2 && i % exp == 0){
                dp[i] = 1;
                exp = i;
            }else{
                dp[i] = dp[exp] + dp[i-exp];
            }
        }
        return dp;
    }
}