小明在学习二进制时，发现了一类不含 101的数，也就是：
将数字用二进制表示，不能出现 101 。
现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含 101 的数
输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。
输出的唯一一行包含一个整数，表示在 [l,r] 区间内一共有几个不含 101 的数。
输入:
1 10
输出:
8
说明:
区间 [1,10] 内，
5 的二进制表示为 101 ，
10的二进制表示为 1010 ，
因此区间 [ 1 , 10 ] 内有 10−2=8 个不含 101的数。
输入:
10 20
输出:
7
说明：
区间 [10,20] 内，
满足条件的数字有 [12,14,15,16,17,18,19]
因此答案为 7。
两种方法。
第一种方法，利用连续整数的二进制变化规律来解题
第二种方法，动态规划
方法一思路：
已知十进制数 n 的二进制序列为 b1，则十进制的 n + 1 对应的二进制序列 b2 为：
b
2
=
{
"
1
"
+
b
1
每一位都变成
0
b
1
中全是
1
将
b
1
中从右往左出现的第一个
0
及其右边的
1
都变成
1
b
1
中含有
0
b2 = \begin{cases} "1" + b1每一位都变成0 & b1中全是 1\\ 将b1中从右往左出现的第一个 0 及其右边的 1 都变成 1 & b1中含有0 \end{cases}
b2={"1"+b1每一位都变成0将b1中从右往左出现的第一个0及其右边的1都变成1b1中全是1b1中含有0
故可推测出是否含有“101”的规律：
b1中为全1时，不会出现“101”
b1中为含有0时，可能会出现“101”（从右往左第一个0变成1后出现“101”、或者从右往左第一个0的左边本来就有“101”）
如下面两幅图所示：
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int left = scanner.nextInt();
int right = scanner.nextInt();
StringBuilder sb = new StringBuilder();
long count = 0;
long sum = right - left + 1;
// 求 left 的二进制
int tmp = left - 1;
while (tmp != 0) {
sb.append(tmp % 2);
tmp /= 2;
}
// 如果 left 对应的二进制中含有“101”，记录 101 的在二进制字符串中的下标
int indexOf = sb.toString().indexOf("101");
int pre = indexOf == -1 ? Integer.MAX_VALUE : indexOf;
while (left <= right) {
int oldLen = sb.length();
int index = oldLen - 1;
// 从右往左找到第一个 0
while (index >= 0 && sb.charAt(index) != '0') {
index--;
}
// 0 的右边的所有 1 替换成 0
if (index < 0) {
// sb中全是 1，则说明二进制的位数需要增加一位才能表示：左边第一位为 1，其余都是 0。且不会出现”101“
pre = pre == sb.length() - 1 ? sb.length() : pre;
sb.append('1');
index = 0;
} else {
if (index - 2 >= 0 && sb.charAt(index - 2) == '1' && sb.charAt(index - 1) == '0') {
// 0 的左边是"10"，则会出现"101": 将 100 --> 101
count++;
// 更新“101”出现的下标： pre
pre = Math.min(pre, index);
} else {
// 在 index 的左边存在 101
if (pre != Integer.MAX_VALUE && pre < index) {
count++;
}
// 更新“101”出现的下标： pre
if (index < pre) {
pre = sb.length();
}
}
}
// 从右往左找到第一个 0 后，把这个 0 改成 1，把 0 的右边的 1 全部改成 0
sb.setCharAt(index++, '1');
while (index < sb.length()) {
sb.setCharAt(index, '0');
index++;
}
left++;
}
System.out.println(sum - count);
}
数位DP的套路解法；
数位DP可以看这个文章：
数位 DP 通用模板，附题单（Python/Java/C++/Go）
static char[] chars;
static int[][][] memo;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int left = scanner.nextInt();
int right = scanner.nextInt();
System.out.println(myDp(right) - myDp(left-1));
}
// 统计出十进制数 [0, num] 中有多少个数的二进制中包含有 "101"
public static int myDp(int num) {
// 初始化记忆数组
chars = Integer.toBinaryString(num).toCharArray();
memo = new int[chars.length][2][2];
for (int i = 0; i < memo.length; i++) {
for (int j = 0; j < 2; j++) {
Arrays.fill(memo[i][j], -1);
}
}
return f(0, 0, 0, true);
}
/**
* 填写二进制序列的第 i 位
* @param i 二进制序列的第 i 位
* @param pre 上一个填写的数字
* @param prepre 上上个填写的数字
* @param isLimit 高位填写过的数字是否和 num 的二进制一样，是的话当前位会受到限制
* @return
*/
private static int f(int i, int pre, int prepre, boolean isLimit) {
// 如果能够成功的填写出长度和 num 一样的二进制数，说明该路径解可行
if (i == chars.length) {
return 1;
}
// 如果已经被搜索过，则直接返回
if (!isLimit && memo[i][pre][prepre] != -1) {
return memo[i][pre][prepre];
}
int res = 0;
int up = isLimit ? chars[i] - '0' : 1;
for (int d = 0; d <= up; d++) {
// 如果当前位填写 1,且前面两位是 0、1，则会组成 "101"
if (!(d == 1 && pre == 0 && prepre == 1)) {
res += f(i + 1, d, pre, isLimit && d == up);
}
}
// 记忆化
if (!isLimit) {
memo[i][pre][prepre] = res;
}
return res;
}