338. Counting Bits

Link

Solution

觀察 i跟 dp[i]的關係

2 010 ​3 011 4 100 5 101 6 110 7 111 若i的lastbit bit為0 則 dp[i] == dp[i >> 1] ( ex. dp[6] == dp[3]) 反之若lastbit為 1， 則 dp[i] == dp[i>>1] + 1 (ex. dp[5] == dp[2] + 1)

dp[i] = dp[i >> 1] + (i&1);

 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 >> 1] + (i & 1);
        }
        return dp;
    }