600-不含连续1的非负整数

600. 不含连续1的非负整数

难度：困难

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 1:

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: $1 <= n <= 10^9$

解题思路:

分析数据构成，以及求解的结果规律，每一个结果都需要上一位的状态，所以，可以使用动态规划，而数位DP正好是记录每一位数状态的求解方式，此题可以使用数位DP的思路来求解。

准备动作:

int型有32位，而每一位有两个状态，可以使用dp[32][2]来进行表示，为避免可能的计算越界，可以将数组开大一些。

定义:

dp[i][j]表示在整形中的第i位，j表示0，1状态时，符合条件的数字数量。

此时得到数据构成，dp[i][0]可以用于表示前i - 1位所有符合规律的数。

得出递推方程

$\left\{\begin{aligned} & dp[i][0] = dp[i - 1][0] + dp[i - 1][1] &因为并不会和上一位产生冲突，上一位任意 \\ & dp[i][1] = dp[i - 1][0] & 会和上一位的1产生冲突，所以只能继承0的结果 \end{aligned} \right.$

例如，4 ： 100 此时dp[3][0]就可以表示此结果。

求解

dp数组只是表示整体的状态，而题目中求的是一个大状态的中的小状态，所以答案应该就是多个小状态的叠加。例如求(0, 20]内满足结果的数。

20： $10100 = (10000)_2 + (100)_2$ 所以，ans = dp[4][0] + dp[2][0] + 1;

即求二进制中从高位到低位中，每一位为1的所有满足条件的子状态的和，如果全部符合，则再加上n自己本身即为所求。

int dp[32][2];
  int q[5] = {1, 2, 3, 3, 4};
  int getlen(int n) {   
      int ret;
      while (n) {
          ++ret;
          n >>= 1;
      }
      return ret;
  }
  int findIntegers(int n) {
      if (n <= 4) {
          return q[n];
      }
      int len = getlen(n); 
      dp[0][0] = 1;
      dp[0][1] = 1;
      for (int i = 0; i < len; i++) {
          dp[i + 1][0] = dp[i][0] + dp[i][1];
          dp[i + 1][1] = dp[i][0];
      }
      int ans = 0, cur = 0, prev = 0;
      
      for (int i = len; i >= 0; --i) {
          cur = (n >> i) & 1;
          if (cur) ans += dp[i][0];
          if (cur && prev) break;
          prev = cur;
          if (i == 0) ++ans;
      }
      return ans;
  }