小明在学习二进制时，发现了一类不含 101的数，也就是：
将数字用二进制表示，不能出现 101 。
现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含 101 的数？
1 10
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">8
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">10 20
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">7
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">解决方法：数字DP
数字DP 的特点：通过将数字转化为二进制数组，用递归的方法枚举可能的二进制组合，同时使用记忆化 (dp) 减少重复计算。
状态定义：
当前位 p。
前一位 prev 和前两位 prev2 的取值，用于判断是否形成了 “101”。
lim：当前位是否被数字的真实二进制表示限制。
转移关系：
当前位可以取值 0 或 1。
如果取值形成 “101” 模式，则跳过。
否则递归到下一位，更新 prev 和 prev2。
剪枝与优化：
当 lim=False 且某状态已计算过（即 dp[p][prev][prev2] > 0），直接返回缓存的结果。
最终计算：分别计算 [1, right] 和 [1, left-1] 的符合条件的数字个数，差值即为结果。
def explore(p, lim, dp, arr, prev, prev2):
"""
数字DP递归函数
:param p: 当前处理的位
:param lim: 当前是否受到上界限制
:param dp: 记忆化数组
:param arr: 二进制数组
:param prev: 前一位的值
:param prev2: 前两位的值
:return: 符合条件的二进制数个数
"""
# 递归终止条件：所有位都处理完，返回1表示找到一种符合条件的组合
if p == len(arr):
return 1
# 如果不受限制且状态已计算过，直接返回缓存结果
if not lim and dp[p][prev][prev2] > 0:
return dp[p][prev][prev2]
# 当前位最大值：如果受限制，则为 `arr[p]`；否则为 1（0 或 1）
max_val = arr[p] if lim else 1
total = 0
# 枚举当前位可能的取值
for v in range(max_val + 1):
# 剪枝：若当前值形成了 "101"，跳过
if v == 1 and prev == 0 and prev2 == 1:
continue
# 递归处理下一位
total += explore(p + 1, lim and v == max_val, dp, arr, v, prev)
# 记录结果到 dp 数组（仅当不受限制时）
if not lim:
dp[p][prev][prev2] = total
return total
def findRange(num):
"""
计算 [1, num] 范围内符合条件的数字个数
:param num: 最大值
:return: 数字个数
"""
# 将数字转换为二进制数组
binary = list(map(int, list(format(num, 'b'))))
# 初始化记忆化数组 dp
dp = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(len(binary))]
# 从最高位开始递归
return explore(0, True, dp, binary, 0, 0)
# 输入范围 [left, right]
left, right = map(int, input().split())
# 计算 [1, right] 和 [1, left-1] 的结果之差
print(findRange(right) - findRange(left - 1))
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">方法
这是一个经典的 数字DP 问题：
状态表示：用一个数组 dp 表示从当前位置到结束位置，符合条件的二进制数的个数。
条件限制：不能出现连续的 “101”。
转移过程：
当前位可以取 0 或 1，但需要满足前两位的状态（用 p1 和 p2 表示前两位）不构成 “101”。
若当前位置取值后导致不满足条件，则跳过。
二进制转换：将给定数字转换成二进制表示，从高位到低位进行DP遍历。
关键细节
lim 参数表示当前位是否受到数字大小的限制。
使用 p1 和 p2 表示当前位的前两位的取值。
通过记忆化搜索（dp 数组）减少重复计算。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 输入左右边界 [l, r]
int l = in.nextInt();
int r = in.nextInt();
// 计算区间内符合条件的数字个数
int res = find(r) - find(l - 1);
System.out.println(res);
}
/**
* 计算在区间 [1, num] 内不包含连续 "101" 的二进制数的个数
*/
public static int find(int num) {
// 将数字转换成二进制数组，例如 10 -> [1, 0, 1, 0]
Integer[] binArr = Arrays.stream(Integer.toBinaryString(num).split(""))
.map(Integer::parseInt)
.toArray(Integer[]::new);
// dp数组: 记忆化搜索，dp[pos][前一位状态1][前两位状态2]
int[][][] dp = new int[binArr.length][2][2];
// 从高位开始进行深度优先搜索
return dfs(0, true, dp, binArr, 0, 0);
}
/**
* 深度优先搜索 (DFS) 进行数字DP
*
* @param pos 当前位置
* @param lim 当前位是否受限制
* @param dp 记忆化数组
* @param binArr 二进制数组
* @param p1 前一位的值
* @param p2 前两位的值
* @return 符合条件的个数
*/
public static int dfs(int pos, boolean lim, int[][][] dp, Integer[] binArr, int p1, int p2) {
// 递归终止条件：当到达二进制的最后一位，返回1
if (pos == binArr.length) return 1;
// 如果不受限制且已经计算过，直接返回记忆化结果
if (!lim && dp[pos][p1][p2] != 0) return dp[pos][p1][p2];
int max = lim ? binArr[pos] : 1; // 当前位的最大可选值（0或1）
int cnt = 0;
// 递归计算下一位
cnt += calcRec(max, pos, lim, dp, binArr, p1, p2);
// 如果不受限制，记录结果到 dp 数组
if (!lim) dp[pos][p1][p2] = cnt;
return cnt;
}
/**
* 遍历当前位可能的取值 (0 或 1)，并判断是否合法
*
* @param max 当前位的最大值
* @param pos 当前位置
* @param lim 是否受限
* @param dp 记忆化数组
* @param binArr 二进制数组
* @param p1 前一位的值
* @param p2 前两位的值
* @return 符合条件的数量
*/
public static int calcRec(int max, int pos, boolean lim, int[][][] dp, Integer[] binArr, int p1, int p2) {
int sum = 0;
for (int i = 0; i <= max; i++) { // 当前位的取值 0 或 1
// 剪枝：若形成 "101" 则跳过
if (i != 1 || p1 != 0 || p2 != 1) {
// 继续递归下一位
sum += dfs(pos + 1, lim && i == max, dp, binArr, i, p1);
}
}
return sum;
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">方法：数字DP
将数字转换为二进制数组：将区间的上界数字转换成二进制数组，从高位到低位逐位处理。
递归枚举每一位的取值：
使用递归深度优先搜索（DFS），逐位选择二进制值（0 或 1）。
当前位的最大取值由是否受限（limited）决定：
如果当前位受限，则取值范围是 0 到该位的实际值。
如果不受限，则取值范围是 0 到 1。
状态转移条件：
如果当前选择形成了 “101” 模式，则跳过该选择。
其他情况下继续递归，并更新状态。
记忆化搜索：
使用 memo 数组记录已经计算过的状态，避免重复计算。
最终结果：分别计算 [1, r] 和 [1, l-1] 范围内符合条件的数字个数，二者相减即为结果。
#include 更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">解决方法
使用数字DP方法，通过逐位处理二进制数字，动态计算符合条件的数字个数。
二进制转换：将数字转为二进制数组，逐位处理。
递归搜索（search 函数）：
遍历每一位的可能取值（0 或 1）。
如果当前选择形成了 “101”，则跳过。
递归地处理下一位，同时更新前两位的状态（last 和 secondLast）。
状态记忆化：
使用 dp 数组存储已经计算过的状态，避免重复计算。
状态由三部分组成：
当前处理的位置 pos。
前一位的值 last。
前两位的值 secondLast。
最终结果：分别计算 [1, R] 和 [1, L-1] 的符合条件的数字个数，二者相减即为答案。
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
// 读取输入的区间 [L, R]
const [L, R] = (await readline()).split(" ").map(Number);
// 计算区间内符合条件的数字个数
const result = countValidNumbers(R) - countValidNumbers(L - 1);
console.log(result);
})();
/**
* 计算 [1, num] 范围内符合条件的数字个数
* @param {number} num 上界数字
* @return {number} 符合条件的数字个数
*/
function countValidNumbers(num) {
// 将数字转换为二进制数组
const binaryArr = num.toString(2).split("").map(Number);
// 初始化 dp 数组
const dp = new Array(binaryArr.length)
.fill(0)
.map(() => new Array(2).fill(0).map(() => new Array(2)));
// 从高位开始递归搜索
return search(0, true, dp, binaryArr, 0, 0);
}
/**
* 递归搜索符合条件的数字个数
* @param {number} pos 当前处理的位数
* @param {boolean} isLimit 当前是否受限
* @param {Array} dp 记忆化数组
* @param {Array} binaryArr 二进制数组
* @param {number} last 前一位的值
* @param {number} secondLast 前两位的值
* @return {number} 符合条件的数字个数
*/
function search(pos, isLimit, dp, binaryArr, last, secondLast) {
// 递归终止条件：所有位处理完，返回 1 表示找到一种合法组合
if (pos === binaryArr.length) return 1;
// 如果不受限制且状态已计算过，直接返回缓存结果
if (!isLimit && dp[pos][last][secondLast]) return dp[pos][last][secondLast];
// 当前位最大值：受限制时为 binaryArr[pos]，否则为 1
const maxDigit = isLimit ? binaryArr[pos] : 1;
let totalCount = 0;
// 枚举当前位的可能取值
for (let digit = 0; digit <= maxDigit; digit++) {
// 剪枝：如果当前位选择形成 "101"，跳过
if (digit === 1 && last === 0 && secondLast === 1) continue;
// 递归处理下一位
totalCount += search(
pos + 1,
isLimit && digit === maxDigit, // 是否继续受限
dp,
binaryArr,
digit, // 当前位变为上一位
last // 上一位变为前两位
);
}
// 如果不受限制，记录结果到 dp 数组
if (!isLimit) dp[pos][last][secondLast] = totalCount;
return totalCount;
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：