给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 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
实现：
可以使用动态规划的思想解决此问题。设dp[i]表示i的二进制表示中1的个数，那么有以下状态转移方程：
- 当i为偶数时，dp[i]=dp[i//2]
- 当i为奇数时，dp[i]=dp[i-1]+1
因为偶数i的二进制表示中，其最低位是0，所以将i向右移一位（相当于除以2），其二进制表示中1的个数不变，即dp[i]=dp[i//2]。 而当i为奇数时，其二进制表示中最低位为1，所以将i-1（相当于将其最低位的1变为0），其二进制表示中1的个数会减少1，即dp[i]=dp[i-1]+1。
以下是Python的实现代码：
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
时间复杂度：O(n)