算法总结9 高阶DP
算法总结9 高阶DP
数位DP
2801. 统计范围内的步进数字数目
以该题作为模板，完成后面的所有题。
class Solution:
def countSteppingNumbers(self, low: str, high: str) -> int:
MOD = 10 ** 9 + 7
def calc(s):
@cache # 记忆化搜索
def dfs(i, pre, is_limit, is_num):
if i == len(s):
return int(is_num)
res = 0
# 1. 直接跳过当前数位
if not is_num: # 可以跳过当前数位
res = dfs(i + 1, pre, False, False)
# 2. 不跳过，那么low，up，is_limit，is_num都要做相应的变化
# 当前位数遍历选值
low = 0 if is_num else 1 # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
up = int(s[i]) if is_limit else 9 # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就会超过 s ）
for d in range(low, up + 1): # 枚举要填入的数字 d
if not is_num or abs(d - pre) == 1: # 第一位数字随便填，其余必须相差 1
res += dfs(i + 1, d, is_limit and d == up, True)
return res % MOD
return dfs(0, 0, True, False)
return (calc(high)-calc(str(int(low)-1))) % MOD
233. 数字 1 的个数
class Solution:
def countDigitOne(self, n: int) -> int:
def cal(s):
@cache
def dfs(i, is_limit, is_num, cnt):
if i == len(s):
return cnt
res = 0
if not is_num:
res = dfs(i+1, False, False, cnt)
low = 0 if is_num else 1
up = int(s[i]) if is_limit else 9
for d in range(low, up+1):
res += dfs(i+1, is_limit and d==up, True, cnt+(d==1))
return res
return dfs(0, True, False, 0)
return cal(str(n))
面试题 17.06. 2出现的次数
class Solution:
def numberOf2sInRange(self, n: int) -> int:
s = str(n)
length = len(s)
@cache
def dfs(i, cnt, is_limit, is_num):
if i == length:
return cnt
res = 0
if not is_num:
res = dfs(i+1, cnt, False, False)
low = 0 if is_num else 1
high = int(s[i]) if is_limit else 9
for d in range(low, high+1):
res += dfs(i+1, cnt+(d==2), is_limit and (d==high), True)
return res
return dfs(0, 0, True, False)
600. 不含连续1的非负整数
class Solution:
def findIntegers(self, n: int) -> int:
s = bin(n)[2:]
length = len(s)
@cache
def dfs(i, pre, is_limit, is_num):
if i == length:
return int(is_num)
res = 0
if not is_num:
res = dfs(i+1, pre, False, False)
low = 0 if is_num else 1
high = int(s[i]) if is_limit else 1
for d in range(low, high+1):
if not (d==pre==1):
res += dfs(i+1, d, is_limit and (d==high), True)
return res
return dfs(0, 0, True, False)+1
902. 最大为 N 的数字组合
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], limit: int) -> int:
s = str(limit)
n = len(s)
@cache
def dfs(i, is_limit, is_num):
if i==n:
return int(is_num)
res = 0
if not is_num:
res = dfs(i+1, False, False)
up = s[i] if is_limit else '9'
for d in digits:
if d<=up:
res += dfs(i+1, is_limit and (d==up), True)
return res
return dfs(0, True, False)
1012. 至少有 1 位重复的数字
1012. 至少有 1 位重复的数字
正难则反
class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
s = str(n)
pre = set()
@cache
def dfs(i, rep, is_limit, is_num):
if i==len(s):
return int(rep and is_num)
res = 0
if not is_num:
res = dfs(i+1, rep, False, False)
low = 0 if is_num else 1
high = int(s[i]) if is_limit else 9
for d in range(low, high+1):
rep = d in pre
pre.add(d)
res += dfs(i+1, rep, is_limit and (d==high), True)
if not rep:
pre.remove(d)
return res
return dfs(0, True, False)