[LeetCode]338 Counting Bits（dp，lowbit）

题目链接：https://leetcode.com/problems/counting-bits/?tab=Description

题意：求[0~n]里各个数的二进制下1的个数。空间时间复杂度都要求O(num)。

很容易想出来递推关系，那就是二进制下x个1是由x-1个1表示的数字中+1过来的，然而如何用快速的方法表示这种关系。回忆到了BIT中的更新方式，很容易想到用lowbit来获取一个唯一的比当前数二进制下1的数少一个1的数。递推式就是f(i)=f(i-lowbit(i))+1。

class Solution {
public:
    int lowbit(int x) {
        return x & (-x);
    }
  vector<int> countBits(int num) {
      vector<int> f(num+1, 0);
      for(int i = 1; i <= num; i++) {
          f[i] = f[i-lowbit(i)] + 1;
      }
      return f;
  }
};