题目定位
它很好地连接了 DP 和位技巧，因为每个答案都能在去掉最低位 1 之后复用更小数字的结果。
关键观察
最经典的转移是 bits[i] = bits[i & (i - 1)] + 1。
目标复杂度
O(n) / O(n)
这题的解法思路怎么拆
1
它很好地连接了 DP 和位技巧，因为每个答案都能在去掉最低位 1 之后复用更小数字的结果。
2
最经典的转移是 bits[i] = bits[i & (i - 1)] + 1。
3
先定义每一位的语义。
4
选一个最自然的位操作来更新该语义。
参考实现
Python# Generic pattern template
x & (x - 1) # clear lowest set bit
x & -x # isolate lowest set bit
x | (1 << i) # set bit i
x & ~(1 << i) # clear bit i
x ^ (1 << i) # toggle bit i
(x >> i) & 1 # read bit i
常见坑点
warning
把每个数字都独立暴力处理，没意识到有递推关系。
warning
不理解 i & (i - 1) 为什么能去掉最低位 1。
高频追问
还有没有基于右移的另一种转移？
为什么它既算 DP 又算位运算？
继续刷相关题
先把 位运算 这个模式刷成体系，再去做更难变体。