数位DP
Copyright
本页面贡献者：CooolKey。 本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。
这类题目中一般给定一些限制条件，
求满足限制条件的第 K 小的数是多少，
或者求在区间 [ L , R ] 内有多少个满足限制条件的数
解题思路：
- 动态规划进行预处理
- 试填法求答案(拼凑思想)
例题一¶
给出一个区间 [ n , m ]（ 0 < n ≤ m < 1000 000 ）
求区间中不含数字4，也不含62的数有多少个
例：
62315 73418 88914 不计算在内
61152 计算在内(6和2不连续)
问题转换：
求 n 以内不含4和62的数的个数
配凑：
4只和自己本身的数位有关
62和相邻两位数有关
所以配凑时需要知道首位数字
设 dp [ i ] [ j ] ，表示开头为 i ，位数为 j 时，满足条件的数的个数
配凑举例：
n = 7563241
7 : +dp [ 0 ] [ 7 ] +dp [ 1 ] [ 7 ] +dp [ 2 ] [ 7 ] +dp [ 3 ] [ 7 ] +dp [ 5 ] [ 7 ] +dp [ 6 ] [ 7 ]
5 : +dp [ 0 ] [ 6 ] +dp [ 1 ] [ 6 ] +dp [ 2 ] [ 6 ] +dp [ 3 ] [ 6 ]
6 : +dp [ 0 ] [ 5 ] +dp [ 1 ] [ 5 ] +dp [ 2 ] [ 5 ] +dp [ 3 ] [ 5 ] +dp [ 5 ] [ 5 ]
3 : +dp [ 0 ] [ 4 ] +dp [ 1 ] [ 4 ] +dp [ 2 ] [ 4 ]
2 : +dp [ 0 ] [ 3 ] +dp [ 1 ] [ 3 ]
4 : +dp [ 0 ] [ 2 ] +dp [ 1 ] [ 2 ] +dp [ 2 ] [ 2 ] +dp [ 3 ] [ 2 ] break
预处理
1 2 | |
优化
可将 i 简化为 0 和 1 两种状态
例题二¶
求第 n 小的，数位中包含666的数
(测试用例不超过1000组，n < 50 000 000)
配凑：
首先求出位数，然后一个一个数字去尝试
例如
已求出答案为8位数
最高位为1时，cnt应加上所有7位的包含666的数
最高位为2时，cnt应加上所有7位的包含666的数
... ...
最高位为6时，cnt应加上所有7位的包含666的数，
再加上开头有连续两个6的不包含666的数
因此需要知道：
所有符合条件的 i 位数的个数
所有不符合条件但开头为66的 i 位数的个数
所有不符合条件但开头为6的 i 位数的个数
所有不符合条件但开头为不为6的 i 位数的个数
预处理：
设 dp [ i ] [ 3 ] ，符合条件的 i 位数
设 dp [ i ] [ j ] ，开头有 j 个6的不符合条件的 i 位数
1 2 3 4 | |