A interesting DP


  • 0
    P

    We know that n & (n-1) will eliminate the first right "one", so the number of "one" of n minus the number of (n & (n-1)) is one.
    Than dp[i] = dp[i & (i-1)] + 1

    vector<int> countBits(int num) {
    vector<int> ret;
    ret.reserve(num);
    ret.push_back(0);
    for(int i = 1; i <= num; i++){
    ret.push_back((ret[(i-1) & i]) + 1);
    }
    return ret;
    }


Log in to reply
 

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