示例 1：

輸入：n = 2
輸出：[0,1,1]
解釋：
0 --> 0
1 --> 1
2 --> 10

示例 2：

輸入：n = 5
輸出：[0,1,1,2,1,2]
解釋：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

• 0 <= n <= 105

實(shí)現(xiàn)：

可以使用動態(tài)規(guī)劃的思想解決此問題。設(shè)dp[i]表示i的二進(jìn)制表示中1的個數(shù)，那么有以下狀態(tài)轉(zhuǎn)移方程：

• 當(dāng)i為偶數(shù)時，dp[i]=dp[i//2]
• 當(dāng)i為奇數(shù)時，dp[i]=dp[i-1]+1

因?yàn)榕紨?shù)i的二進(jìn)制表示中，其最低位是0，所以將i向右移一位（相當(dāng)于除以2），其二進(jìn)制表示中1的個數(shù)不變，即dp[i]=dp[i//2]。 而當(dāng)i為奇數(shù)時，其二進(jìn)制表示中最低位為1，所以將i-1（相當(dāng)于將其最低位的1變?yōu)?），其二進(jìn)制表示中1的個數(shù)會減少1，即dp[i]=dp[i-1]+1。

以下是Python的實(shí)現(xiàn)代碼：

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n+1)
        for i in range(1, n+1):
            if i % 2 == 0:
                dp[i] = dp[i//2]
            else:
                dp[i] = dp[i-1] + 1
        return dp

時間復(fù)雜度：O(n)