1. 问题描述:
2. 思路分析:
3. 代码如下:
from typing import List
class Solution:
# f[i][j]表示总共有i位最高位为j的方案数目
def init(self, N: int, f: List[List[int]]):
# 只有一位数字的方案
for i in range(10):
# 主要是不是4说明就是满足要求
if i != 4:
f[1][i] = 1
for i in range(2, N):
# 枚举总共有i位数字最高位填j
for j in range(10):
# 最高位为4的那么直接跳过
if j == 4: continue
# 枚举次高位填k
for k in range(10):
# 筛选掉不满足方案次高位为4或者是上一位与当前这一位构成了62说明不满足条件跳过
if j == 4 or (j == 6 and k == 2): continue
# 方案合法累加到结果即可
f[i][j] += f[i - 1][k]
# 求解区间[0, n]中满足题目要求的方案数目
def dp(self, n: int, f: List[List[int]]):
# 特判一下n = 0的情况
if n == 0: return 1
nums = list()
while n > 0:
nums.append(n % 10)
n //= 10
# last记录前缀信息, 因为下一位只与上一位是有关系的所以使用last记录上一位数字是什么
res, last = 0, 0
for i in range(len(nums) - 1, -1, -1):
x = nums[i]
# 枚举最高位填0~x-1的情况
for k in range(x):
# 当前这一位是4或者与上一位构成了62那么直接跳过
if k == 4 or (last == 6 and k == 2): continue
res += f[i + 1][k]
# 判断这一位是否是4或者构成了62如果是说明进入循环的下一位的时候右边的分支是不合法的
if x == 4 or (last == 6 and x == 2):
break
else:
# 更新当前的last进入循环的下一位的时候表示上一位数字
last = x
# 最右边的那个分支
if i == 0: res += 1
return res
def process(self):
# 预处理列表f
N = 11
f = [[0] * 10 for i in range(N)]
while True:
n, m = map(int, input().split())
if n == 0 and m == 0: break
self.init(N, f)
print(self.dp(m, f) - self.dp(n - 1, f))
if __name__ == "__main__":
Solution().process()