递推

状态表示: f[i]表示i的二进制表示中 1的个数。

例如：i的二进制表示：110111
i的二进制中1的个数可以看成去掉最后一位后1的个数，再判断最后一位是否是1即可。因为i去掉一位后一定是<= i的，所以可以递推。即f[i] = f[i >> 1] + (i & 1)

初始化：0二进制表示没有1，即f[0] = 0

$ 时间复杂度O(N)$

参考文献

lc究极班

AC代码

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> f(n + 1);
        f[0] = 0;
        for (int i = 1 ; i <= n ; i ++)
            f[i] = f[i >> 1] + (i & 1);
        return f;
    }
};