LeetCode 338. Counting Bits 比特位計數：O(n) 動態規劃最優解

題目描述

給定非負整數 num，對每個 0 ≤ i ≤ num 計算其二進制表示中 1 的個數，返回數組。要求 O(n) 時間、O(n) 空間，不使用內建函數 (如 __builtin_popcount)。

核心規律發現

觀察 0~15 的結果：

i   : 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
bits: 0  1  1  2  1  2  2  3  1  2  2  3  2  3  3  4

關鍵洞察：

• [1] = [0] + 1
• [2,3] = [0,1] + 1
• [4,5,6,7] = [0,1,2,3] + 1
• [8...15] = [0...7] + 1

通式：dp[i] = dp[i - highestPowerOf2] + 1，其中 highestPowerOf2 是 ≤ i 的最大 2 的冪次。

O(n) 動態規劃代碼

class Solution {
public:
    vector countBits(int num) {
        vector dp(num + 1, 0);
        int offset = 1;  // 當前 2 的冪次
        
        for (int i = 1; i <= num; ++i) {
            if (offset * 2 == i) offset = i;  // 遇到新的 2 的冪次
            dp[i] = dp[i - offset] + 1;
        }
        return dp;
    }
};

另一視角：奇偶性規律

// 奇數：最低位為 1 → dp[i] = dp[i>>1] + 1
// 偶數：最低位為 0 → dp[i] = dp[i>>1]
for (int i = 1; i <= num; ++i) {
    dp[i] = dp[i >> 1] + (i & 1);
}

更簡潔，同樣 O(n)，利用右移丟棄最低位的性質。

複雜度與優勢

總結

本題核心在於發現重疊子問題與最優子結構：

1. 將區間按 2 的冪次劃分，高位相同，低位循環
2. 或利用最低位奇偶性，右移後子問題已解決
3. 兩種 DP 思路均達到理論下界 O(n)

面試時優先寫奇偶性版本：代碼極短、邏輯清晰、性能最優。