https://leetcode.cn/problems/counting-bits/ (opens new window) 需要注意的点

1. python, // ，商的向下取整
2. 若dp[i]是偶数，那么dp[i] = dp[i//2]，比如2和4， 3和6

若dp[i]是奇数，那么dp[i] = dp[i-1] +1, 不进位加1

class Solution:
    def countBits(self, n: int) -> List[int]:
        '''
        0 --> 0
        1 --> 1
        2 --> 10
        3 --> 11
        4 --> 100
        5 --> 101
        6 --> 110
        7 --> 111
        8 --> 1000
        9 --> 1001
        10 -->1010
        11 -->1011
        '''
        dp = [0 for _ in range(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