338. 比特位计数

解法一：动态规划

dp[i] 表示 i 的二进制形式中 1 的个数。因此有以下DP方程。

我的解法和官方题解的第二种是一个思路。

class Solution {
    public int[] countBits(int num) {
        // dp[i]表示i的二进制形式中1的个数
        int[] dp = new int[num + 1];
        dp[0] = 0;
        for (int i = 1, x = 1; i <= num; ++i) {
            // i=2^k, dp[i]=1
            if (i == x) {
                dp[i] = 1;
                x <<= 1;
            } else {
                dp[i] = 1 + dp[i - (x >> 1)];
            }
        }
        return dp;
    }
}

解法二：动态规划

参考官方题解的三、四两种方法。第三种我觉得还是可以想到的，第四种实在是太巧妙了。

class Solution {
    public int[] countBits(int num) {
        // dp[i]表示i的二进制形式中1的个数
        int[] dp = new int[num + 1];
        for (int i = 1; i <= num; ++i) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}

class Solution {
    public int[] countBits(int num) {
        // dp[i]表示i的二进制形式中1的个数
        int[] dp = new int[num + 1];
        for (int i = 1; i <= num; ++i) {
            dp[i] = dp[i & (i - 1)] + 1;
        }
        return dp;
    }
}