338. Counting Bits

这道题让我们输出从1~num这几个数的bit表达1的数量。 直接计算肯定是可以的 那么怎么得到O(N)的算法 我们可以观察

一个数的二进位表达式可以“拆分”为右移一位的1的数量和最低位 所以递推式就出来了。DP主要问题是怎么把当前的问题

拆分为同一个的小规模问题

public class Solution {
  public int[] countBits(int num) {
        int[] tab = new int[num + 1];
        //默认tab[0] = 0 所以多开一位的数组
        for(int i = 1; i <= num; i++){
            // add last bit (i&1) with the number of bits in i/2 (equivalent to i>>1)
            tab[i] = (i & 1) + tab[i >> 1];
        }
        return tab;
    }
}