# Leetcode 338. Counting Bits

## 題解

### 動態規劃

#### Bottom up

class Solution:
    def countBits(self, n: int) -> List[int]:
        def isPowerOfTwo(n: int) -> bool:
            return n & (n - 1) == 0
        if n < 2:
            return [i for i in range(n+1)]
        output = [0,1]
        i = 2
        pow = 1
        while i <= n:
            output.append(output[i - (2 ** pow)] + 1)
            i += 1
            if isPowerOfTwo(i): pow += 1
        return output