不含连续 1 的非负整数

数位 DP：

  1. 预处理
  2. 按位做
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int findIntegers(int n) {
    vector<int> num;
    // 转成二进制，num[0] 是最低位
    while (n) num.push_back(n % 2), n /= 2;
    // f[i][0] 表示一共有 i 位，且最高位为 0，总共有多少种合法方案
    // f[i][1] 表示一共有 i 位，且最高位为 1，总共有多少种合法方案
    vector<vector<int>> f(num.size() + 1, vector<int>(2));
    f[1][0] = f[1][1] = 1;
    for (int i = 2; i <= num.size(); i++) {
      f[i][0] = f[i - 1][0] + f[i - 1][1];
      f[i][1] = f[i - 1][0];
    }
    int res = 0;
    // 从高到低遍历每一位
    for (int i = num.size(), last = 0; i; i--) {
      int x = num[i - 1];
      if (x) {
        // 如果是 1，那么如果这位填 0，比当前数小，累加 f[i][0] 到答案
        res += f[i][0];
        if (last) return res;
      }
      last = x;
    }
    // 如果输入的数本身是合法的，需要加上这个数，所以 +1
    return res + 1;
  }
};