LeetCode 第 338 题：比特位计数（Counting Bits） 题目描述 给你一个整数 n，要求计算从 0 到 n 的每个整数的二进制表示中 1 的个数，并返回一个长度为 n+1 的数组，其中数组的第 i 个元素是 i 的二进制表示中 1 的个数。 解题思路 我们将循序渐进地分析这个问题，从最直观的方法开始，逐步优化到高效的动态规划解法。 步骤 1：暴力解法（逐个计算） 最直接的方法是遍历 0 到 n 的每个整数 i，对每个 i 计算其二进制表示中 1 的个数。计算单个整数 i 的二进制中 1 的个数，可以通过不断除以 2（或使用位运算 i & (i-1)）来实现。 时间复杂度：O(n * k)，其中 k 是整数二进制表示的位数（平均约为 log n）。 空间复杂度：O(1)，不考虑输出数组。 这种方法虽然简单，但对于较大的 n 可能不够高效。 步骤 2：观察规律，引入动态规划 我们可以利用已知结果来推导未知结果，避免重复计算。观察二进制数的特点： 如果一个数 i 是偶数，它的二进制表示最后一位是 0，因此 i 中 1 的个数与 i/2 相同。 如果一个数 i 是奇数，它的二进制表示最后一位是 1，因此 i 中 1 的个数等于 i/2 中 1 的个数加 1。 这可以形式化为： 如果 i 是偶数：bits[ i] = bits[ i/2 ] 如果 i 是奇数：bits[ i] = bits[ i/2 ] + 1 由于 i/2 等价于 i >> 1（右移一位），我们可以统一写成： bits[ i] = bits[ i >> 1 ] + (i & 1) 其中 i & 1 可以判断奇偶性（奇数得 1，偶数得 0）。 步骤 3：动态规划的实现 基于上述规律，我们可以从 0 开始逐步计算到 n： 初始化数组 dp，长度为 n+1，dp[ 0 ] = 0。 对于 i 从 1 到 n： dp[ i] = dp[ i >> 1 ] + (i & 1) 这种方法每个数只需常数时间操作，因此： 时间复杂度：O(n) 空间复杂度：O(1)（不考虑输出数组） 步骤 4：另一种动态规划思路（利用最低有效位） 除了上述方法，还可以利用 i & (i-1) 运算，该运算将 i 的最低位的 1 变为 0。因此，i 中 1 的个数比 i & (i-1) 多 1。即： bits[ i] = bits[ i & (i-1) ] + 1 实现步骤： dp[ 0 ] = 0 对于 i 从 1 到 n： dp[ i] = dp[ i & (i-1) ] + 1 这种方法同样高效，且更直接地利用了位操作。 总结 通过动态规划，我们避免了重复计算，将问题优化到线性时间复杂度。两种动态规划方法都是有效的，你可以根据个人偏好选择其中一种。关键点是识别二进制数中 1 的个数与更小数值的关联性，从而利用已计算结果。