01. 数位 DP 知识
01. 数位 DP 知识
1. 数位 DP 简介
1.1 数位 DP 简介
数位动态规划:简称为「数位 DP」,是一种与数位相关的一类计数类动态规划问题,即在数位上进行动态规划。这里的数位指的是个位、十位、百位、千位等。
数位 DP 一般用于求解给定区间
数位 DP 通常有以下几个特征:
- 题目会提供一个查询区间(有时也会只提供区间上界)来作为统计限制。
- 题目中给定区间往往很大(比如
),无法采用朴素的方法求解。 - 题目中给定的给定的限定条件往往与数位有关。
- 要求统计满足特定条件的数值个数,或者用于求解满足特定条件的第
小数。
题目要求一段区间
在使用「前缀和思想」思想后,问题转换为计算区间
接下来就要用到数位 DP 的基本思想。
数位 DP 的基本思想:将区间数字拆分为数位,然后逐位进行确定。
我们通过将区间上的数字按照数位进行拆分,然后逐位确定每一个数位上的可行方案,从而计算出区间内的可行方案个数。
数位 DP 可以通过「记忆化搜索」的方式实现,也可以通过「迭代递推」的方式实现。因为数位 DP 中需要考虑的参数很多,使用「记忆化搜索」的方式更加方便传入参数,所以这里我们采用「记忆化搜索」的方式来实现。
在使用「记忆化搜索」的时候,需要考虑的参数有:
- 当前枚举的数位位置(
)。 - 前一位数位(或前几位数位)的情况,比如前几位的总和(
)、某个数字出现次数( )、前几位所选数字集合(通常使用「状态压缩」的方式,即用一个二进制整数 来表示)等等。 - 前一位数位(或前几位数位)是否等于上界的前几位数字(
),用于限制本次搜索的数位范围。 - 前一位数位是否填了数字(
),如果前一位数位填了数字,则当前位可以从 开始填写数字;如果前一位没有填写数字,则当前位可以跳过,或者从 开始填写数字。 - 当前位数位所能选择的最小数字(
)和所能选择的最大数字( )。
对应代码如下:
class Solution:
def digitDP(self, n: int) -> int:
# 将 n 转换为字符串 s
s = str(n)
@cache
# pos: 第 pos 个数位
# state: 之前选过的数字集合。
# isLimit: 表示是否受到选择限制。如果为真,则第 pos 位填入数字最多为 s[pos];如果为假,则最大可为 9。
# isNum: 表示 pos 前面的数位是否填了数字。如果为真,则当前位不可跳过;如果为假,则当前位可跳过。
def dfs(pos, state, isLimit, isNum):
if pos == len(s):
# isNum 为 True,则表示当前方案符合要求
return int(isNum)
ans = 0
if not isNum:
# 如果 isNumb 为 False,则可以跳过当前数位
ans = dfs(pos + 1, state, False, False)
# 如果前一位没有填写数字,则最小可选择数字为 0,否则最少为 1(不能含有前导 0)。
minX = 0 if isNum else 1
# 如果受到选择限制,则最大可选择数字为 s[pos],否则最大可选择数字为 9。
maxX = int(s[pos]) if isLimit else 9
# 枚举可选择的数字
for x in range(minX, maxX + 1):
# x 不在选择的数字集合中,即之前没有选择过 x
if (state >> x) & 1 == 0:
ans += dfs(pos + 1, state | (1 << x), isLimit and x == maxX, True)
return ans
return dfs(0, 0, True, False)
接下来,我们通过一道简单的例题来具体了解一下数位 DP 以及解题思路。
1.2 统计特殊整数
1.2.1 题目大意
描述:给定一个正整数
要求:求区间
说明:
- 特殊整数:如果一个正整数的每一个数位都是互不相同的,则称它是特殊整数。
。
示例:
- 示例 1:
输入:n = 20
输出:19
解释:1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
- 示例 2:
输入:n = 5
输出:5
解释:1 到 5 所有整数都是特殊整数。
1.2.2 解题思路
思路 1:动态规划 + 数位 DP
将 def dfs(pos, state, isLimit, isNum):
表示构造第
- 从
dfs(0, 0, True, False)
开始递归。dfs(0, 0, True, False)
表示:- 从位置
开始构造。 - 初始没有使用数字(即前一位所选数字集合为
)。 - 开始时受到数字
对应最高位数位的约束。 - 开始时没有填写数字。
- 从位置
- 如果遇到
,表示到达数位末尾,此时:- 如果
,说明当前方案符合要求,则返回方案数 。 - 如果
,说明当前方案不符合要求,则返回方案数 。
- 如果
- 如果
,则定义方案数 ,令其等于 ,即: 。 - 如果遇到
,说明之前位数没有填写数字,当前位可以跳过,这种情况下方案数等于 位置上没有受到 位的约束,并且之前没有填写数字时的方案数,即:ans = dfs(i + 1, state, False, False)
。 - 如果
,则当前位必须填写一个数字。此时:- 根据
和 来决定填当前位数位所能选择的最小数字( )和所能选择的最大数字( ), - 然后根据
来枚举能够填入的数字 。 - 如果之前没有选择
,即 不在之前选择的数字集合 中,则方案数累加上当前位选择 之后的方案数,即:ans += dfs(pos + 1, state | (1 << x), isLimit and x == maxX, True)
。state | (1 << x)
表示之前选择的数字集合 加上 。isLimit and x == maxX
表示 位受到之前位限制和 位限制。 表示 位选择了数字。
- 根据
思路 1:代码
class Solution:
def countSpecialNumbers(self, n: int) -> int:
# 将 n 转换为字符串 s
s = str(n)
@cache
# pos: 第 pos 个数位
# state: 之前选过的数字集合。
# isLimit: 表示是否受到选择限制。如果为真,则第 pos 位填入数字最多为 s[pos];如果为假,则最大可为 9。
# isNum: 表示 pos 前面的数位是否填了数字。如果为真,则当前位不可跳过;如果为假,则当前位可跳过。
def dfs(pos, state, isLimit, isNum):
if pos == len(s):
# isNum 为 True,则表示当前方案符合要求
return int(isNum)
ans = 0
if not isNum:
# 如果 isNumb 为 False,则可以跳过当前数位
ans = dfs(pos + 1, state, False, False)
# 如果前一位没有填写数字,则最小可选择数字为 0,否则最少为 1(不能含有前导 0)。
minX = 0 if isNum else 1
# 如果受到选择限制,则最大可选择数字为 s[pos],否则最大可选择数字为 9。
maxX = int(s[pos]) if isLimit else 9
# 枚举可选择的数字
for x in range(minX, maxX + 1):
# x 不在选择的数字集合中,即之前没有选择过 x
if (state >> x) & 1 == 0:
ans += dfs(pos + 1, state | (1 << x), isLimit and x == maxX, True)
return ans
return dfs(0, 0, True, False)
思路 1:复杂度分析
- 时间复杂度:
,其中 为给定整数。 - 空间复杂度:
。
2. 数位 DP 的应用
2.1 至少有 1 位重复的数字
2.1.1 题目链接
2.1.2 题目大意
描述:给定一个正整数
要求:返回在
说明:
。
示例:
- 示例 1:
输入:n = 20
输出:1
解释:具有至少 1 位重复数字的正数(<= 20)只有 11。
- 示例 2:
输入:n = 100
输出:10
解释:具有至少 1 位重复数字的正数(<= 100)有 11,22,33,44,55,66,77,88,99 和 100。
2.1.3 解题思路
思路 1:动态规划 + 数位 DP
正向求解在
将 def dfs(pos, state, isLimit, isNum):
表示构造第
- 从
dfs(0, 0, True, False)
开始递归。dfs(0, 0, True, False)
表示:- 从位置
开始构造。 - 初始没有使用数字(即前一位所选数字集合为
)。 - 开始时受到数字
对应最高位数位的约束。 - 开始时没有填写数字。
- 从位置
- 如果遇到
,表示到达数位末尾,此时:- 如果
,说明当前方案符合要求,则返回方案数 。 - 如果
,说明当前方案不符合要求,则返回方案数 。
- 如果
- 如果
,则定义方案数 ,令其等于 ,即: 。 - 如果遇到
,说明之前位数没有填写数字,当前位可以跳过,这种情况下方案数等于 位置上没有受到 位的约束,并且之前没有填写数字时的方案数,即:ans = dfs(i + 1, state, False, False)
。 - 如果
,则当前位必须填写一个数字。此时:- 根据
和 来决定填当前位数位所能选择的最小数字( )和所能选择的最大数字( ), - 然后根据
来枚举能够填入的数字 。 - 如果之前没有选择
,即 不在之前选择的数字集合 中,则方案数累加上当前位选择 之后的方案数,即:ans += dfs(pos + 1, state | (1 << d), isLimit and d == maxX, True)
。state | (1 << d)
表示之前选择的数字集合 加上 。isLimit and d == maxX
表示 位受到之前位限制和 位限制。 表示 位选择了数字。
- 根据
- 最后的方案数为
n - dfs(0, 0, True, False)
,将其返回即可。
思路 1:代码
class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
# 将 n 转换为字符串 s
s = str(n)
@cache
# pos: 第 pos 个数位
# state: 之前选过的数字集合。
# isLimit: 表示是否受到选择限制。如果为真,则第 pos 位填入数字最多为 s[pos];如果为假,则最大可为 9。
# isNum: 表示 pos 前面的数位是否填了数字。如果为真,则当前位不可跳过;如果为假,则当前位可跳过。
def dfs(pos, state, isLimit, isNum):
if pos == len(s):
# isNum 为 True,则表示当前方案符合要求
return int(isNum)
ans = 0
if not isNum:
# 如果 isNumb 为 False,则可以跳过当前数位
ans = dfs(pos + 1, state, False, False)
# 如果前一位没有填写数字,则最小可选择数字为 0,否则最少为 1(不能含有前导 0)。
minX = 0 if isNum else 1
# 如果受到选择限制,则最大可选择数字为 s[pos],否则最大可选择数字为 9。
maxX = int(s[pos]) if isLimit else 9
# 枚举可选择的数字
for d in range(minX, maxX + 1):
# d 不在选择的数字集合中,即之前没有选择过 d
if (state >> d) & 1 == 0:
ans += dfs(pos + 1, state | (1 << d), isLimit and d == maxX, True)
return ans
return n - dfs(0, 0, True, False)
思路 1:复杂度分析
- 时间复杂度:
。 - 空间复杂度:
。
2.2 数字 1 的个数
2.2.1 题目链接
2.2.2 题目大意
描述:给定一个整数
要求:计算所有小于等于
说明:
。
示例:
- 示例 1:
输入:n = 13
输出:6
- 示例 2:
输入:n = 0
输出:0
2.2.3 解题思路
思路 1:动态规划 + 数位 DP
将 def dfs(pos, cnt, isLimit):
表示构造第
- 从
dfs(0, 0, True)
开始递归。dfs(0, 0, True)
表示:- 从位置
开始构造。 - 初始数字
出现的个数为 。 - 开始时受到数字
对应最高位数位的约束。
- 从位置
- 如果遇到
,表示到达数位末尾,此时:返回数字 出现的个数 。 - 如果
,则定义方案数 ,令其等于 ,即: 。 - 如果遇到
,说明之前位数没有填写数字,当前位可以跳过,这种情况下方案数等于 位置上没有受到 位的约束,并且之前没有填写数字时的方案数,即:ans = dfs(i + 1, state, False, False)
。 - 如果
,则当前位必须填写一个数字。此时:- 因为不需要考虑前导
所以当前位数位所能选择的最小数字( )为 。 - 根据
来决定填当前位数位所能选择的最大数字( )。 - 然后根据
来枚举能够填入的数字 。 - 方案数累加上当前位选择
之后的方案数,即:ans += dfs(pos + 1, cnt + (d == 1), isLimit and d == maxX)
。cnt + (d == 1)
表示之前数字 出现的个数加上当前位为数字 的个数。isLimit and d == maxX
表示 位受到之前位 位限制。
- 因为不需要考虑前导
- 最后的方案数为
dfs(0, 0, True)
,将其返回即可。
思路 1:代码
class Solution:
def countDigitOne(self, n: int) -> int:
# 将 n 转换为字符串 s
s = str(n)
@cache
# pos: 第 pos 个数位
# cnt: 之前数字 1 出现的个数。
# isLimit: 表示是否受到选择限制。如果为真,则第 pos 位填入数字最多为 s[pos];如果为假,则最大可为 9。
def dfs(pos, cnt, isLimit):
if pos == len(s):
return cnt
ans = 0
# 不需要考虑前导 0,则最小可选择数字为 0
minX = 0
# 如果受到选择限制,则最大可选择数字为 s[pos],否则最大可选择数字为 9。
maxX = int(s[pos]) if isLimit else 9
# 枚举可选择的数字
for d in range(minX, maxX + 1):
ans += dfs(pos + 1, cnt + (d == 1), isLimit and d == maxX)
return ans
return dfs(0, 0, True)
思路 1:复杂度分析
- 时间复杂度:
。 - 空间复杂度:
。
参考资料
来源:https://github.com/itcharge/LeetCode-Py