LeetCode 第 338 题：比特位计数（Counting Bits） 题目描述 给你一个整数 n ，请返回一个长度为 n + 1 的数组 ans ，其中 ans[i] 表示 i 的二进制表示中 1 的个数（0 ≤ i ≤ n）。要求算法的时间复杂度为 O(n) 。 示例 输入：n = 2 输出：[ 0,1,1 ] 解释：0 的二进制是 "0"，有 0 个 1；1 的二进制是 "1"，有 1 个 1；2 的二进制是 "10"，有 1 个 1。 解题思路 如果直接对每个数单独计算二进制中 1 的个数（如用位运算循环右移统计），时间复杂度为 O(n log n) ，不满足要求。我们需要利用已知结果来推导新值，具体通过动态规划实现。 关键观察 奇偶性规律 ： 偶数 i 的二进制末尾是 0，因此 i 的二进制中 1 的个数等于 i/2 的二进制中 1 的个数（右移一位等价于除以 2）。 例如： i=6 （二进制 "110"）与 i/2=3 （二进制 "11"）的 1 的个数相同。 奇数 i 的二进制末尾是 1，因此 i 的二进制中 1 的个数等于 i-1 的二进制中 1 的个数加 1（因为 i-1 是偶数，末尾由 0 变为 1）。 例如： i=7 （二进制 "111"）比 i-1=6 （二进制 "110"）多一个 1。 动态规划递推式 ： 设 dp[i] 表示数字 i 的二进制中 1 的个数。 如果 i 是偶数： dp[i] = dp[i/2] 如果 i 是奇数： dp[i] = dp[i-1] + 1 合并为一行代码： dp[i] = dp[i >> 1] + (i & 1) （右移一位等价于除以 2， i & 1 判断奇偶性）。 步骤详解 初始化 ：创建数组 dp 长度为 n+1 ，且 dp[0] = 0 （0 的二进制没有 1）。 遍历计算 ：从 i=1 到 n ，根据递推式填充 dp[i] ： 计算 i/2 的 1 的个数（通过 dp[i >> 1] ）； 加上 i 的最低位是否为 1（通过 i & 1 ）。 返回结果 ：最终 dp 数组即为所求。 示例推导（n=5） i=0: dp[ 0 ] = 0 i=1: dp[ 1] = dp[ 0 ] + (1&1) = 0 + 1 = 1 i=2: dp[ 2] = dp[ 1 ] + (2&1) = 1 + 0 = 1 i=3: dp[ 3] = dp[ 1 ] + (3&1) = 1 + 1 = 2 i=4: dp[ 4] = dp[ 2 ] + (4&1) = 1 + 0 = 1 i=5: dp[ 5] = dp[ 2 ] + (5&1) = 1 + 1 = 2 结果：[ 0,1,1,2,1,2 ] 复杂度分析 时间复杂度： O(n) ，只需遍历一次数组。 空间复杂度： O(n) ，用于存储结果数组（不算输出空间则为 O(1) ）。 关键点总结 利用二进制数的结构性（奇偶性）避免重复计算。 动态规划的核心是找到子问题关系：当前数的 1 的个数可由更小数的结果推导。