Counting Bits

解題說明

題目描述：給定整數 n，回傳長度為 n+1 的陣列，其中 ans[i] 為 i 的二進位中 1 的個數。

解題思路：利用動態規劃的位元關係。對於任意整數 i，i >> 1（右移一位即除以 2）的 1 的個數已知，再加上 i 最低位（i & 1）即可得到 dp[i] = dp[i >> 1] + (i & 1)。這利用了子問題重疊性質，O(n) 時間計算所有結果。

時間複雜度：O(n) — 每個數字只計算一次。

空間複雜度：O(n) — 儲存所有結果的 DP 陣列（即輸出本身）。

1. Create dp array of size n+1, all zeros
2. For i from 1 to n:
   a. dp[i] = dp[i >> 1] + (i & 1)
3. Return dp

朴素 O(n log n)：對各 i 逐一計數位元（每個數 O(log i)）。正確但更慢。

最高 2 的冪：dp[i] = dp[i - highestPowerOf2(i)] + 1。需追蹤最高冪；右移法更簡潔。