Here is my DP C++ solution

• ``````class Solution {
public:
vector<int> countBits(int num) {
/*
00000000  0 0
00000001  1 1
00000010  1 2
00000011  2 3
00000100  1 4
00000101  2 5
00000110  2 6
00000111  3 7
00001000  1 8
00001001  2 9
00001010  2 10
00001100  2 11
00001101  3 12
00001110  3 13
00001111  4 14
00010000  1 15

DP:
idx:        0 1 2 3 4 5
last 2 pow: 0 1 2 2 4 4
bit count : 0 1 2 1 2 2

DP(n) = 1 + DP(value after resetting msb set bit)
= 1 + DP(n - closest 2 pow x)
*/
std::vector<int> dp(num+1, 0); // include zero
if (num == 0) return dp;
int last2 = 1;
for (int i=1; i<dp.size(); ++i) {
if ((i & (i-1)) == 0) {
last2=i;
dp[i] = 1;
} else {
dp[i] = 1 + dp[i-last2];
}
}
return dp;
}
};``````

• good solution!, little suggestion, the if statement inside the for loop could be more simple as:

``````if ((i & (i - 1)) == 0) {
last2 = i;
}
dp[i] = 1 + dp[i - last2];
``````

• Good suggestion

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.