Share my c++ solution, dp, 380ms


  • 0
    X
    vector<int> countBits(int num){
    vector<int> dp(num+1, 0); 
    if(num == 0)
        return dp; 
    else if(num == 1){ 
        dp[1] = 1;
        return dp; 
    }   
    
    dp[1] = 1;
    int curPower = 1;
    for (int i = 2; i <= num; i++) {
        if(i == curPower*2){
            dp[i] = 1;
            curPower *= 2;
        }else{
            dp[i] = dp[curPower] + dp[i-curPower];
        }   
    }   
    return dp; 
    

    }


Log in to reply
 

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