Here is my DP C++ solution


  • 6
    P
    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;
        }
    };

  • 1
    Y

    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];
    

  • 0
    P

    Good suggestion


Log in to reply
 

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