题目分析

一个简单的题目，正是因为思路简单，所以会忽略一些技巧。先提示一下，可以通过动态规划进行求解，小伙伴们先尝试一下如何实现。

暴力法

对每一个元素都求二进制表示，然后统计1的个数，因为求二进制表示需要log(n)的时间。所以算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$**。

1
2
3

class Solution:
    def countBits(self, num):
        return [bin(x).count('1') for x in range(num + 1)]

动态规划

动态规划并不一定需要有固定的写法，同学们可能存在一种思维定势，如一维DP，就是i从0到n，找i和i - 1的关系，二维DP，就是i从0到n，j从0到n或者从0到i，找i和j的关系。其实动态规划只是记忆化的搜索过程，只要是以前保存的结果，都可以在$O(1)$的复杂度将其取出。

我们已知前k - 1个数二进制表示中1的个数，要计算第k个数的二进制表示中1的个数，如何可以通过$O(1)$的时间复杂度计算呢？

在大于0的数中，至少有一位为1，而且在**位运算中有一个操作可以删除最后一位的1，这个操作就是x & (x - 1)，小伙伴们可以想一想为什么可以这样做？将k的最后一位的1删除以后，必然比k小，一定在记录之中，而且只少了一个1，因此状态转移方程为
$$dp[i] = dp[i & (i - 1)] + 1$$
算法的时间复杂度为O(n)，空间复杂度为O(n)**。

class Solution:
    def countBits(self, num):
        dp = [0] * (num + 1)
        for i in range(1, num + 1):
            dp[i] = dp[i & (i - 1)] + 1
        return dp

刷题总结

有没有写出来呢？小伙伴们要打破思维定势，寻找更加精妙的解法。