LC 8013. 范围中美丽整数的数目
https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/description/
这次算是自己琢磨出来怎么写数位dp的，实现中有两个点，分别都是和isStart有关系的：
- 只有isStart=False,的时候，才可以继续以isStart=False递归下去，否则就要开始枚举具体数字了。
- 只有isStart=True的时候，才能枚举left被用于odd/even. 如果isStart=False,那么只能粗略判断(odd + left) < even
然后就是这个状态中value必须取模k, 否则这个状态数量就太大了。
class Solution:
def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
def OkOddEven(isStart, odd, even, left):
if isStart:
for x in range(0, left + 1):
if (odd + x) == (even + left - x):
return True
return False
else:
if (odd + left) < even or (even + left) < odd:
return False
return True
def search(ss):
import functools
@functools.cache
def f(i, isLimit, isStart, odd, even, value):
# print(i, isLimit, isStart, odd, even, value)
if i == len(ss):
if not isStart: return 0
if odd == even and value % k == 0:
# print(value)
return 1
return 0
left = len(ss) - i
if not OkOddEven(isStart, odd, even, left):
return 0
ans = 0
if not isStart:
ans += f(i + 1, True, False, odd, even, value)
from_value = 1 if not isStart else 0
to_value = int(ss[i]) if not isLimit else 9
for x in range(from_value, to_value + 1):
ans += f(i + 1, isLimit or x < int(ss[i]), isStart or x != 0,
odd + (x % 2), even + (x + 1) % 2,
# value * 10 + x)
(value * 10 + x) % k)
return ans
return f(0, False, False, 0, 0, 0)
h = search(str(high))
l = search(str(low - 1))
ans = h - l
return ans