338. Counting Bits - cocoder39/coco39_LC GitHub Wiki
Take n = 1010011(b) as an example, f(n) = f(101001) + 1 = f(n/2) + (n & 1); T = O(N) and S = O(N) where N = num.
vector<int> countBits(int num) {
vector<int> dp(num + 1);
dp[0] = 0;
for (int i = 1; i <= num; i++) {
dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
}