# C++, intuitive dp sln

• ``````class Solution {
public:
vector<int> countBits(int num)
{
// validate input
vector<int> rs(num+1,0);
rs[0] = 0;
rs[1] = 1;
if(num<=1) return rs;

// T={2^31-1,2^30-1,.....,2^1-1};
vector<int> T;
for(int i = 31; i>=1; i--)
{
T.push_back(pow(2,i)-1);
}

// dp
for(int i = 2; i<=num; i++)
{

int j = 0;
// set the left most non-zero bit of i to 0 to acquire j
for(int k = 0; k<T.size(); k++)
{
if(i>T[k])
{
j = i&T[k];
break;
}
}
// the number of 1s in num i equals to 1 + the number of 1s in num j
// e.g. i = 1101, then j = 0101, thus rs[i] = 1 + rs[j]. we already solved
// subproblem rs[j] in previous calculation (dp).
rs[i] = 1 + rs[j];
}
return rs;
}
``````

short explanation:
For a number i = 1101, we calculate the numbers of 1s in it (rs[i]) by checking our previous calculation result rs[j] ( j= 0101, j is calculated by setting the left most non-zero bit of i to 0: [1]101 to [0]101) and +1 to that result (rs[i] = 1 + rs[j]) . Then we calculate the whole rs with initialization rs[0] = 0, and rs[1] = 1 bottom up.

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