来源0x3f：https://space.bilibili.com/206214

视频讲解：https://www.bilibili.com/video/BV1rS4y1s721

引用：【洛谷日报#84】数字组成的奥妙——数位dp：https://zhuanlan.zhihu.com/p/50791875

文章目录

• 数位DP（本质就是枚举每个数）
• • 一、记搜过程
  • 二、状态设计
  • • 1、前导0标记 isNum（看0是否会影响数字结构决定用不用isNum）
    • 2、最高位标记 islimit
  • 三、 dp 值的记录和使用（记忆化搜索）
• 数位DP练习题
• • （理解模板题）[2376. 统计特殊整数](https://leetcode.cn/problems/count-special-integers/)
  • [902. 最大为 N 的数字组合](https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/)
  • [233. 数字 1 的个数](https://leetcode.cn/problems/number-of-digit-one/)
  • [面试题 17.06. 2出现的次数](https://leetcode.cn/problems/number-of-2s-in-range-lcci/)
  • [1012. 至少有 1 位重复的数字](https://leetcode.cn/problems/numbers-with-repeated-digits/)
  • [600. 不含连续1的非负整数](https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/)
  • [788. 旋转数字](https://leetcode.cn/problems/rotated-digits/)

数位DP（本质就是枚举每个数）

【引入】
首先我们要清楚数位dp解决的是什么问题：

求出在给定区间[A,B][A,B][A,B] 内，符合条件 f(i)f(i)f(i)的数 iii 的个数。条件 f(i)f(i)f(i) 一般与数的大小无关，而与数的组成有关

由于数是按位dp，数的大小对复杂度的影响很小

【设计搜索】

这里我们使用记忆化搜索实现数位dp。本质上记搜其实就是dp，下文会重点介绍dp值的使用和记录

一、记搜过程

从起点向下搜索，到最底层得到方案数，一层一层向上返回答案并累加，最后从搜索起点得到最终答案。

对于[l,r][l,r][l,r]区间问题，我们一般把他转化为两次数位dp,即找[0,r][0,r][0,r]和[0,l−1][0,l−1][0,l−1]两段，再将结果相减就得到了我们需要的[l,r][l,r][l,r]

二、状态设计

如果理解了上述过程，我们需要考虑的就是怎样判断现在在哪一层，怎样判断当前的状态——这就需要我们传进一些参量。

dfsdfsdfs函数需要哪些参量？

1. 首先是数位dp基本的量数字位数idxidxidx**，记录答案的 **ststst **，**最高位限制 islimitislimitislimit（这个后面会讲）
2. 我们还需要一个**判断判断前导0的标记 **isNumisNumisNum（这个后面也会讲）
3. 由于数位dp解决的大多是数字组成问题，所以经常要比较当前位和前一位或前几位的关系（根据题意而定），所以一般在dfs()中也要记录前一位或前几位数preprepre方便比较。
4. 除此之外还可以传进更多参量以区分状态，视题意而定。

【细节分析】

1、前导0标记 isNum（看0是否会影响数字结构决定用不用isNum）

由于我们要搜的数可能很长，所以我们的直接最高位搜起

举个例子：假如我们要从[0,1000][0,1000][0,1000]找任意相邻两数相等的数

显然 111,222,888 等等是符合题意的数

但是我们发现右端点 1000 是四位数

因此我们搜索的起点是 0000 ，而三位数的记录都是 0111,0222,0888 等等

而这种情况下如果我们直接找相邻位相等则 0000 符合题意而 0111,0222,0888 都不符合题意了

所以我们要加一个前导0标记

1. 如果当前位 isNum=false 而且当前位也是0，那么当前位也是前导0， pos+1 继续搜；
2. 如果当前位 isNum=false 但当前位不是0，则本位作为当前数的最高位， pos+1 继续搜；（注意这次根据题意st或其他参数可能发生变化）

当然前导0有时候是不需要判断的，上述的例子是一个有关数字结构上的性质，0会影响数字的结构，所以必须判断前导0；而如果我们研究的是数字的组成（例如这个数字有多少个1之类的问题），0并不影响我们的判断，这样就不需要前导0标记了。总之，这个因题而异，并不是必须要标记（当然记了肯定是不会出错的）

2、最高位标记 islimit

我们知道在搜索的数位搜索范围可能发生变化；

举个例子：我们在搜索 [0,555] 的数时，显然最高位搜索范围是0−50-50−5，而后面的位数的取值范围会根据上一位发生变化：

1. 当最高位是 1~4 时，第二位取值为 [0,9] ;
2. 当最高位是 5 时，第二位取值为 [0,5] （再往上取就超出右端点范围了）

为了分清这两种情况，我们引入了 islimit 标记：

1. 若当前位 islimit=true 而且已经取到了能取到的最高位时，下一位 islimit=true ；
2. 若当前位 islimit=true 但是没有取到能取到的最高位时，下一位 islimit=false ；
3. 若当前位 islimit=false 时，下一位 islimit=false 。

我们设这一位的标记为 islimit ，这一位能取到的最大值为 up，则下一位的标记就是 idx==up && islimit （ idx 枚举这一位填的数）

三、 dp 值的记录和使用（记忆化搜索）

最后我们考虑dp数组下标记录的值

本文介绍数位dp是在记忆化搜索的框架下进行的，每当找到一种情况我们就可以这种情况记录下来，等到搜到后面遇到相同的情况时直接使用当前记录的值。

dp数组的下标表示的是一种状态，只要当前的状态和之前搜过的某个状态完全一样，我们就可以直接返回原来已经记录下来的dp值。

再举个例子

假如我们找 [0,123456] 中符合某些条件的数

假如当我们搜到 1000??1000??1000??时，dfs从下返上来的数值就是当前位是第5位，前一位是0时的方案种数，搜完这位会向上反，这是我们可以记录一下：当前位第5位，前一位是0时，有这么多种方案种数

当我们继续搜到 1010??1010??1010?? 时，我们发现当前状态又是搜到了第5位，并且上一位也是0，这与我们之前记录的情况相同，这样我们就可以不继续向下搜，直接把上次的dp值返回就行了。

注意，我们返回的dp值必须和当前处于完全一样的状态，这就是为什么dp数组下标要记录 idx,pre 等参量了。

最重要的来了————————————————————

接着上面的例子，范围 [0,123456]

如果我们搜到了 1234?? ，我们能不能直接返回之前记录的：当前第 5 位，前一位是 4 时的dp值？

答案是否定的，我们发现，这个状态的dp值被记录时，当前位也就是第 5 位的取值是[0,9][0,9][0,9][0,5][0,5][0,5] ，方案数一定比之前记录的dp值要小。

当前位的取值范围为什么会和原来不一样呢？

如果你联想到了之前所讲的知识，你会发现：现在的 islimit=true ，最高位有取值的限制。

因此我们可以得到一个结论：当 islimit=true 时，不能记录和取用dp值！

类似上述的分析过程，我们也可以得出：当 isNum=false 时，也不能记录和取用dp值！

p.s.当然没有这么绝对的说……因题而异的说……

数位DP练习题

附：力扣上的数位 DP 题目（0x3f）

• 233. 数字 1 的个数
• 面试题 17.06. 2出现的次数
• 600. 不含连续1的非负整数
• 902. 最大为 N 的数字组合
• 1012. 至少有 1 位重复的数字
• 1067. 范围内的数字计数（会员题）

（理解模板题）2376. 统计特殊整数

难度困难52

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。

示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

提示：

• 1 <= n <= 2 * 109

class Solution {char s[];int dp[][]; // i, mask 记忆化搜索不需要记忆islimit和isnumpublic int countSpecialNumbers(int n) {s = Integer.toString(n).toCharArray();int m = s.length;dp = new int[m][1<<10]; // [1<<10]=[1024]for(int i = 0; i < m; i++) Arrays.fill(dp[i], -1);//islimit初始化为true：因为如果填false 后面就可以随便填了//					初始化为true,表示后面填内容受到约束(0位上本来就是0==>true)//isNum初始化为false：因为什么数字都没填,不是数字return f(0, 0, true, false);}// 返回从 i 开始填数字,i前面填的数字的集合是mask,能构造出的特殊整数的数目// isLimit表示前面填的数字是否都是n对应位上的,//          如果为true,那么当前位至多为(int)s[i],否则至多为9// is_num表示前面是否填了数字(是否跳过),//          若为ture,那么当前位可以从0开始,如果为false,那么当前位可以跳过,或者从1开始int f(int i, int mask, boolean isLimit, boolean isNum){if(i == s.length) //到了递归终点return isNum ? 1 : 0;if(!isLimit && isNum && dp[i][mask] >= 0) return dp[i][mask];int res = 0;// isNum==false，若前面没有填数字（跳过了），可以继续跳过当前数位（不填数字）// 此时这里的isLimit=false,因为此时前面填的数字不是n位对应上限,可以填0-9if(!isNum) res = f(i + 1, mask, false, false);// 枚举要填入的数字 dfor(int d = isNum ? 0 : 1, up = isLimit? s[i]-'0' : 9; d <= up; d++){if((mask >> d & 1) == 0){ // d不在mask中【这里的判断具体看题目要求】res += f(i+1, mask | (1 << d), isLimit & (d == up), true);}}if(!isLimit && isNum) dp[i][mask] = res;return res;}
}

902. 最大为 N 的数字组合

难度困难246

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

示例 1：

输入：digits = ["1","3","5","7"], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：

输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

示例 3:

输入：digits = ["7"], n = 8
输出：1

提示：

• 1 <= digits.length <= 9
• digits[i].length == 1
• digits[i] 是从 '1' 到 '9' 的数
• digits 中的所有值都 不同
• digits 按 非递减顺序 排列
• 1 <= n <= 109

https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/solution/shu-wei-dp-tong-yong-mo-ban-xiang-xi-zhu-e5dg/

题解：这里可以不需要mask，因为没有约束，唯一的约束是选择数字的范围要在digits中

class Solution {String[] digits;char s[];int dp[];public int atMostNGivenDigitSet(String[] digits, int n) {this.digits = digits;s = Integer.toString(n).toCharArray();dp = new int[s.length];Arrays.fill(dp, -1);return f(0, true, false);}int f(int i, boolean isLimit, boolean isNum){if(i == s.length) // 如果填了数字，则为 1 种合法方案return isNum ? 1 : 0;if(!isLimit && isNum && dp[i] >= 0) // 在不受到任何约束的情况下，返回记录的结果，避免重复运算return dp[i];int res = 0;if(!isNum) // 前面不填数字，那么可以跳过当前数位，也不填数字// isLimit 改为 false，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束// isNum 仍然为 false，因为没有填任何数字res = f(i + 1, false, false);char up = up = isLimit ? s[i] : '9'; // 根据是否受到约束，决定可以填的数字的上限for(String d : digits){if(d.charAt(0) > up) break; // d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环res += f(i+1, isLimit & (d.charAt(0) == up), true);}if(!isLimit && isNum) dp[i] = res; // 在不受到任何约束的情况下，记录结果return res;}
}

233. 数字 1 的个数

难度困难495

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

• 0 <= n <= 109

题解：前导零对结果没有影响，不需要记录isNum

• cache[i][cnt1]表示从左往右第i位，已经出现了cnt1个1，cnt1当然要记忆化

class Solution{char s[];int[][] cache;public int countDigitOne(int n) {s = Integer.toString(n).toCharArray();int m = s.length;cache = new int[m][m];for(int i = 0; i < m; i++) Arrays.fill(cache[i], -1);return f(0, true, 0);}public int f(int i, boolean isLimit, int cnt1){if(i == s.length){return cnt1;}if(!isLimit&& cache[i][cnt1] >= 0) return cache[i][cnt1];int res = 0;int up = isLimit ? s[i] - '0' : 9;for(int d = 0; d <= up; d++){res += f(i + 1, isLimit && up == d, cnt1 + ((d == 1) ? 1 : 0));}if(!isLimit) cache[i][cnt1] = res;return res;}
}

面试题 17.06. 2出现的次数

难度困难68

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

示例:

输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)

提示：

• n <= 10^9

题解：同233.数字 1 的个数

class Solution {char s[];int[][] cache;public int numberOf2sInRange(int n) {s = Integer.toString(n).toCharArray();int m = s.length;cache = new int[m][1 << 10];for(int i = 0; i < m; i++) Arrays.fill(cache[i], -1);return f(0, 0, true);}public int f(int i, int cnt2, boolean isLimit){if(i == s.length) return cnt2;if(!isLimit && cache[i][cnt2] >= 0) return cache[i][cnt2];int res = 0;int up = isLimit ? s[i] - '0' : 9;for(int d = 0; d <= up; d++){res += f(i + 1, cnt2 + (d == 2 ? 1 : 0), isLimit && d == up);}if(!isLimit) cache[i][cnt2] = res;return res;}
}

1012. 至少有 1 位重复的数字

难度困难141

给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

示例 1：

输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。

示例 2：

输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。

示例 3：

输入：n = 1000
输出：262

提示：

• 1 <= n <= 109

题解：数字有重复和不重复两个状态，记忆化要记忆这个状态，同时mask记录数字是否出现过

class Solution {char s[];int[][][] cache; // i mask repeat(数字有重复和不重复两个状态)public int numDupDigitsAtMostN(int n) {s = Integer.toString(n).toCharArray();int m = s.length;cache = new int[m][1 << 10][2];return f(0, 0, true, false, 0);}public int f(int i, int mask, boolean isLimit, boolean isNum, int repeat){if(i == s.length)return isNum && (repeat == 1) ? 1 : 0;if(!isLimit && isNum && cache[i][mask][repeat] > 0) return cache[i][mask][repeat];int res = 0;if(!isNum) res = f(i+1, mask, false, false,repeat);int up = isLimit ? s[i] - '0' : 9;for(int d = isNum ? 0 : 1; d <= up; d++){res += f(i+1, mask|(1 << d), isLimit && d == up, true, repeat | (mask >> d) & 1);}if(!isLimit && isNum) cache[i][mask][repeat] = res;return res;}
}

600. 不含连续1的非负整数

难度困难310

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。

示例 1:

输入: n = 5
输出: 5
解释: 
下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。

示例 2:

输入: n = 1
输出: 2

示例 3:

输入: n = 2
输出: 3

提示:

• 1 <= n <= 109

题解：与前面题目的区别在于枚举n的二进制位，如果i-1位是1，则i位不能填1了

class Solution {char s[];int[][] cache;public int findIntegers(int n) {// 注意这里，将n转为二进制表示，然后枚举每个二进制位// 如果i-1位是1，则i位不能是1// 记忆化缓存i和ispre两个状态s = Integer.toBinaryString(n).toCharArray();int m = s.length;cache = new int[m][2];for(int i = 0; i < m; i++) Arrays.fill(cache[i], -1);return f(0, false, true);}public int f(int i, boolean isPre1, boolean isLimit){if(i == s.length){return 1;}if(!isLimit && cache[i][isPre1 ? 1 : 0] >= 0) return cache[i][isPre1 ? 1 : 0];int res = 0;for(int d = 0, up = isLimit ? s[i] - '0' : 1; d <= up; d++){if(d == 1 && isPre1) continue; // i-1位是1了，i位跳过1res += f(i+1, d == 1, isLimit && d == up);}if(!isLimit) cache[i][isPre1 ? 1 : 0] = res;return res;}
}

788. 旋转数字

难度中等197

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

示例：

输入: 10
输出: 4
解释: 
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

提示：

• N 的取值范围是 [1, 10000]。

class Solution {// 好数中不能有3，4，7，且至少包含2，5，6，9中的一个static int[] DIFFS = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};char s[];int[][] cache;public int rotatedDigits(int n) {s = Integer.toString(n).toCharArray();int m = s.length;cache = new int[m][2];for(int i = 0; i < m; i++) Arrays.fill(cache[i], -1);return f(0, 0, true);}// hasDiff表示前面填的数字是否包含2，5，6，9中的至少一个public int f(int i, int hasDiff, boolean isLimit){// 只有包含 2/5/6/9 才算一个好数if(i == s.length) return hasDiff;if(!isLimit && cache[i][hasDiff] >= 0) return cache[i][hasDiff];int res = 0;int up = isLimit ? s[i]-'0' : 9;for(int d = 0; d <= up; d++){if(DIFFS[d] != -1){ // d 不是 3/4/7res += f(i+1, hasDiff | DIFFS[d], isLimit && d == up);}}if(!isLimit) cache[i][hasDiff] = res;return res;}
}