核心思想
数位dp的尝试方式并不特殊，绝大多数都是线性展开，类似从左往右的尝试 。大量在数组上进行线性展开的题目，数位dp是在数字的每一位上进行线性展开而已 不同的题目有不同的限制，解题核心在于：可能性的整理、排列组合的相关知识
解决数位dp的问题 推荐使用记忆化搜索的方式，可能性的展开会很好写，不必刻意追求进一步改写， 递归写出来问题就解决了，位数多就挂缓存，位数不多甚至不挂缓存也能通过
仔细从第2题开始看，会发现这个数位dp都开始有一种模版代码思路的感觉，只不过根据题意改一点点条件判定的东西。
例题
1、统计各位数字都不同的数字个数
题目描述： 给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。
示例 1：
输入：n = 2 输出：91 解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。
示例 2：
输入：n = 0 输出：1
提示：
0 <= n <= 8
解题思路：
没有什么额外的东西，纯粹的数学计算
注意的是：
当位数过多时，最高位只能从1 2 3 4 5 6 7 8 9中共9个数子挑选
其余位，皆可以从0 1 2 3 4 5 6 7 8 9中共10个数字中挑选
代码如下：
package main.java.class084;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_CountNumbersWithUniqueDigits
* @description: 统计各位数字都不同的数字个数
* // 给你一个整数n，代表十进制数字最多有n位
* // 如果某个数字，每一位都不同，那么这个数字叫做有效数字
* // 返回有效数字的个数，不统计负数范围
* // 测试链接 : https://leetcode.cn/problems/count-numbers-with-unique-digits/
* @author: zs宝
* @create: 2025-10-09 10:50
* @Version 1.0
**/public class Code01_CountNumbersWithUniqueDigits {
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if(n==0){
return 1;
}
if(n==1){
return 10;
}
int ans=10;
for(int i=2,sum=9,temp=9;i<=n;i++,temp--){
//当有多位时，如假设n=4,那么我们需要计算出所有不同位的符合条件的数字个数
//n=4: 9*9*8*7
//n=3: 9*9*8 //n=2: 9*9 十位可选：1 2 3 4 5 6 7 8 9，个位可选 0 1 2 3 4 5 6 7 8 9 //n=1: 10 sum=sum*temp;
ans+=sum;
}
return ans;
}
}
}2、最大为N的数字组合
题目描述： 给定一个按 非递减顺序 排列的数字数组 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
解题思路：
这道题其实就是一个数学问题，
当我们组成的数值位数小于给定数值时，做一个计算统计
当我们组成的数值位数与给定数值相同时，对每一位做一个比较的判断
小于，则后续位的数值可以任意挑选
等于，则后续位需要判断考虑
大于，直接放弃
思路虽然简单，但是code缺不是那么容易组织结构来写
代码如下
package main.java.class084;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_NumbersAtMostGivenDigitSet
* @description: 最大为N的数字组合
* // 给定一个按 非递减顺序 排列的数字数组 digits
* // 已知digits一定不包含'0'，可能包含'1' ~ '9'，且无重复字符
* // 你可以用任意次数 digits[i] 来写的数字
* // 例如，如果 digits = ['1','3','5']
* // 我们可以写数字，如 '13', '551', 和 '1351315'
* // 返回 可以生成的小于或等于给定整数 n 的正整数的个数
* // 测试链接 : https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/
* @author: zs宝
* @create: 2025-10-09 11:18
* @Version 1.0
**/public class Code02_NumbersAtMostGivenDigitSet {
class Solution {
public int atMostNGivenDigitSet(String[] digits, int n) {
return atMostNGivenDigitSet2(digits,n);
}
//纯暴力递归的解法
public int atMostNGivenDigitSet1(String[] strs, int num) {
//首先求出给定的数值num到底有几位len，并通过len拿到一个offset，利用len和offset可以快速得到每位的数值
int temp=num/10;
//长度
int len=1;
//offset将等于10^(len-1)
int offset=1;
while(temp>0){
temp=temp/10;
len++;
offset*=10;
}
//将字符串中的数值全部准转到int数组中去
int m=strs.length;
int[]digits=new int[m];
for(int i=0;i<m;i++){
digits[i]=Integer.valueOf(strs[i]);
}
return f1(digits,num,len,offset,0,0);
}
/**
digits:可以用的数字数组
num:数字组成的范围
len:当前来到num的第几位，还剩len位没有决定，数值n-0-->高-底
offset：辅助计算每一位的数值是多少，由len得来
free：为0时表示前一位与num的对应位相同，当前位即后面位不可以任意数字；为1时表示前一位小于num的对应位数值，当前位即后面的位可以任意数字
fix:为0时表示前面位取消，即前一位没有取任何数值，为1时表示前面位有取数值
*/
public int f1(int[]digits,int num,int len,int offset,int free,int fix){
//已经所有位都遍历过了
if(len==0){
return fix==1?1:0;
}
//计算当前位的数值
int cur=(num/offset)%10;
int ans=0;
//若fix==0,看看接着为0的情况
if(fix==0){
ans+=f1(digits,num,len-1,offset/10,1,0);
}
//free为0，前面位数值与num相同，fix必等于1
if(free==0){
for(int i=0;i<digits.length;i++){
if(digits[i]<cur){
//当前选的值小于cur，则后续位的值随便选什么都可以
ans+=f1(digits,num,len-1,offset/10,1,1);
}else if(digits[i]==cur){
ans+=f1(digits,num,len-1,offset/10,0,1);
}else{
break;
}
}
}else{
//free为1，任意值都能取
ans+=digits.length*f1(digits,num,len-1,offset/10,1,1);
}
return ans;
}
//针对暴力递归进行优化
//上述很多中情况其实可以提前通过数学计算求得，不用走递归，递归过程中很多也可以直接通过数学计算拿到值，减少递归次数
//首先一个就是假设num有7位，如果我们取得值位数根本不足7位，那么这些数值的数量完全可以通过数学计算得来，不用一个个递归，那么暴力递归的fix变量就没有了
//其次就是当我们的数值取和num一样的位数时，当前一位小于num位上的数，那么后面位的数值可以随便取，这个数量也能通过数学计算得来，减少递归的次数，所以暴力递归的free也可没取消了
public int atMostNGivenDigitSet2(String[] strs, int num) {
//首先求出给定的数值num到底有几位len，并通过len拿到一个offset，利用len和offset可以快速得到每位的数值
int temp=num/10;
//长度
int len=1;
//offset将等于10^(len-1)
int offset=1;
while(temp>0){
temp=temp/10;
len++;
offset*=10;
}
//将字符串中的数值全部准转到int数组中去
int m=strs.length;
int[]digits=new int[m];
for(int i=0;i<m;i++){
digits[i]=Integer.valueOf(strs[i]);
}
//打表，一方面求出位数小于num的位数的数量，一方面为后续当前一位小于num位上的数，那么后面位的数值可以随便取时，做一个数量的计算
// cnt[i] : 已知前缀比num小，剩下i位没有确定，请问前缀确定的情况下，一共有多少种数字排列
// cnt[0] = 1，表示后续已经没有了，前缀的状况都已确定，那么就是1种
// cnt[1] = m
// cnt[2] = m * m // cnt[3] = m * m * m int[]cnts=new int[len];
cnts[0]=1;
int ans=0;
for(int i=m,k=1;k<len;k++,i*=m){
cnts[k]=i;
ans+=i;
}
//后续递归，就是取得位数和num一样时的情况
return ans+f2(digits,cnts,num,len,offset);
}
public int f2(int[]digits,int[]cnts,int num,int len,int offset){
//已经所有位都遍历过了
if(len==0){
return cnts[0];
}
//计算当前位的数值
int cur=(num/offset)%10;
int ans=0;
//由于不再寻妖考虑暴力递归的free和fix，所以这里直接循环
for(int i:digits){
if(i<cur){
//直接从打的表中拿就是
ans+=cnts[len-1];
}else if(i==cur){
ans+=f2(digits,cnts,num,len-1,offset/10);
}else{
break;
}
}
return ans;
}
}
}3、统计整数数目
题目描述： 给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：
num1 <= x <= num2min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后的结果。
注意，digit_sum(x) 表示 x 各位数字之和。
示例 1：
输入：num1 = "1", num2 = "12", min_sum = 1, max_sum = 8 输出：11 解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。
示例 2：
输入：num1 = "1", num2 = "5", min_sum = 1, max_sum = 5 输出：5 解释：数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。
提示：
1 <= num1 <= num2 <= 10^221 <= min_sum <= max_sum <= 400
解题思路：
这个题是上一个题的变形，这个题不再给可选的数字数组，意味着可以从0-9的范围选择数字
要求找到num1-num2的符合要求的数字个数
可以先找到0-num2的符合要求的整数个数ans2
再找到0-num1-1的符合要求的整数个数ans1
最后用ans2-ans1
但是要注意这里给的是数值是字符串的形式，我们很有可能无法将其转为int或者long，长度可能特别长
因此我们可以换一个思路，找到0-num1的符合要求的整数个数ans3
用ans2-ans3, 如何判断num1是否为一个符合要求的数值，是的话ans2-ans3+1
这里的符合要求是取的数值的各个位上的累加和在min_sum -max_sum之间，这样的话，其实就是在上一个题的基础上加上一个sum值的判断
这里我最开始在想的时候一直在向位数和nums相同时用上一个题的思路很好做，但是位数小与nums时呢？这里0-9都可以选，高位选0的时候不就把位数小于nums的情况包含了吗。犯蠢了。
这里总结下一个疑问，为什么第而题的递归要有fix这个判定前方位取不取值的情况，而第3题却不用？
这是因为第二题题目要求的取数值digest范围不能包括0,
而本题第3题的取值范围是有0的，当前缀一直取0时，就相当于前缀位不用
代码如下
package main.java.class084;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_CountOfIntegers
* @description: 统计整数数目
* // 给你两个数字字符串 num1 和 num2 ，以及两个整数max_sum和min_sum
* // 如果一个整数 x 满足以下条件，我们称它是一个好整数
* // num1 <= x <= num2
* // min_sum <= digit_sum(x) <= max_sum * // 请你返回好整数的数目
* // 答案可能很大，答案对 1000000007 取模
* // 注意，digit_sum(x)表示x各位数字之和
* // 测试链接 : https://leetcode.cn/problems/count-of-integers/
* @author: zs宝
* @create: 2025-10-10 09:57
* @Version 1.0
**/public class Code03_CountOfIntegers {
class Solution {
public static int MOD = 1000000007;
public static int MAXN = 23;
public static int MAXM = 401;
public static int[][][] dp = new int[MAXN][MAXM][2];
public static char[] nums;
public static int min, max,len;
public static void build() {
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXM; j++) {
dp[i][j][0] = -1;
dp[i][j][1] = -1;
}
}
}
public static int count(String num1, String num2, int min_sum, int max_sum) {
min=min_sum;
max=max_sum;
//计算0-num2的符合条件的整数有哪些
nums=num2.toCharArray();
len=num2.length();
build();
int ans=0;
ans=(ans+f(0,0,0))%MOD;
//统计0-num1的符合条件的整数有哪些
nums=num1.toCharArray();
len=num1.length();
build();
ans=(ans-f(0,0,0)+MOD)%MOD;
//检查num1本身符合要求否
if(check()){
ans=(ans+1)%MOD;
}
return ans;
}
/**
从高位逐渐向低位走
i:表示来到的第几位，0-nums.length,数值越小位数越高
sum：前面几位数值的累加和
free:为1时，当前位及后面位的数值可以为任意值，为0时当前位及后面位上的数值要珍重考虑（针对选出来的数值最终要小于等于nums）
*/
public static int f(int i,int sum,int free){
//各个位上的数值累计累加和要在min-max之间
if(sum>max){
return 0;
}
if(sum+(len-i)*9<min){
return 0;
}
if(i==len){
return 1;
}
if(dp[i][sum][free]!=-1){
return dp[i][sum][free];
}
int ans=0;
//当前位nums的数值位多少
int cur=nums[i]-'0';
//不可以自由选择
if(free==0){
//选的数值小于nums的对应位数值
for(int k=0;k<cur;k++){
if(k<cur){
ans=(ans+f(i+1,sum+k,1))%MOD;
}
}
//选的数值等于nums的对应位数值
ans=(ans+f(i+1,sum+cur,0))%MOD;
}else{
for(int k=0;k<=9;k++){
ans=(ans+f(i+1,sum+k,1))%MOD;
}
}
dp[i][sum][free]=ans;
return ans;
}
public static boolean check(){
int sum=0;
for(int i=0;i<len;i++){
sum+=(nums[i]-'0');
}
return sum>=min && sum<=max;
}
}
}4、完全没有重复的数字个数
题目描述： 如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 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
解题思路：
这个题与前面几个题的解题思路十分相关，尤其是第2题，这个题只是多了一个每个位上面的数字都不相同的判定条件
这个每个位都不相同的判定可以使用位运算的方式
在前面几个题的基础上加上关于为不同的判定即可
但是还需要注意一个情况，这个情况就是我写这道题的2个解法所犯错的地方，关于0的判定
在第一种暴力递归解法的时候，
我们优先考虑了让当前位接着不取数值的情况(fix== 0)，这就相当于当前位取0，只是这个0无效而已
所以对于后续对当前位的考虑，我们不能再考虑0
所以就有了start这个东西，进行遍历循环的起始考虑
只有当前一位取了值后，后面的位考虑情况才能包含0
在第二种解法的时候，
我们已经对位低于nums时做了数学计算，算出所有可能性, 后续递归计算都是考虑位数和nums相同时的情况
所以在从最高位往最低位递归的过程中，考虑最高位的时候，不能考虑0，这个是需要判定的
因此我们设置了start这个遍历循环的起始位置
代码如下
package main.java.class084;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_CountSpecialIntegers
* @description: 完全没有重复的数字个数
* // 给定正整数n，返回在[1, n]范围内每一位都互不相同的正整数个数
* // 测试链接 : https://leetcode.cn/problems/count-special-integers/
* @author: zs宝
* @create: 2025-10-10 11:26
* @Version 1.0
**/public class Code04_CountSpecialIntegers {
class Solution {
public int countSpecialNumbers(int nums) {
return countSpecialNumbers2(nums);
}
public int countSpecialNumbers1(int nums) {
//先求出这个nums是多少位的
int temp = nums / 10;
int len = 1;
int offset = 1;
while (temp > 0) {
temp /= 10;
len++;
offset *= 10;
}
return f1(nums, len, len, offset, 0, 0, 0);
}
/**
* i：来到了第几位，值越大，位数越高
* offset:辅助求解nums第i位的数值
* free:为1时，在数值在比nums小的这个条件上，当前位的数值可以随便选，；为0时，在比nums这个数小的条件上,当前位数值不能随便选
* fix:为1时，前一位取了数值；为0，前一位没有取数值
* status:位运算，表示那些数字使用过，0表示未使用过，1表示使用过
*/
public int f1(int nums, int len, int i, int offset, int free, int fix, int status) {
if (i == 0) {
return fix == 1 ? 1 : 0;
}
if (status == (1 << 10) - 1) {
return 0;
}
int ans = 0;
//计算前缀接着为0的情况
if (fix == 0) {
ans += f1(nums, len, i - 1, offset / 10, 1, 0, status);
}
//求解当前i位上的数值
int cur = (nums / offset) % 10;
//根据fix计算后续遍历的起始位，若前面的fix=0，则当前位计算不能选0（前面fix==0已经把当前位为0的可能计算过了，后面当前位就不可以再选0了）
int start = fix == 0 ? 1 : 0;
//前一位的数值与nums上对应位的数值相同，当前位的数值不能随便选（在数值小于nums的条件上）
if (free == 0) {
for (int p = start; p < cur; p++) {
//注意每一位上的数值不能相同
if ((status & (1 << p)) == 0) {
ans += f1(nums, len, i - 1, offset / 10, 1, 1, status | (1 << p));
}
}
//数值选择等于cur时
if (!(fix == 0 && cur == 0) && (status & (1 << cur)) == 0) {
ans += f1(nums, len, i - 1, offset / 10, 0, 1, status | (1 << cur));
}
} else {
//前一位的数值小于nums上对应位的数值，当前位的数值可以随便选（在数值小于nums的条件上）
for (int p = start; p <= 9; p++) {
//注意每一位上的数值不能相同
if ((status & (1 << p)) == 0) {
ans += f1(nums, len, i - 1, offset / 10, 1, 1, status | (1 << p));
}
}
}
return ans;
}
//由暴力递归优化而来，用数学的提前打表计算一些情况的数量，从而减少递归的次数
public int countSpecialNumbers2(int nums) {
//先求出这个nums是多少位的
int temp = nums / 10;
int len = 1;
int offset = 1;
while (temp > 0) {
temp /= 10;
len++;
offset *= 10;
}
//计算比nums位数低的数值，且满足每一个数位都是 互不相同 的条件
int ans = 0;
for (int i = 1, k = 10, sum = 9; i < len; i++, k--, sum *= k) {
ans += sum;
}
//打表辅助计算，当位数与nums相同时，若从第几位开始在比nums小的条件下可以任意取值时，兼顾每位数不同的要求
//通过数学计算在当前位开始能有多少种可能
//比如 len=4 //则 cnt[4]不计算
//cnt[3]=9*8*7
//cnt[2]=8*7 //cnt[1]=7 //cnt[0]=1表示前缀已经确定，数值已经确定了，只有1种情况
int[] cnts = new int[len];
cnts[0] = 1;
for (int i = 1, k = 10 - len + 1; i < len; i++, k++) {
cnts[i] = cnts[i - 1] * k;
}
//现在位数比nums低的已经全部算到了ans中，接下来就只用计算位数以nums相同的情况
return ans + f2(cnts, nums, len, offset, 0, 0);
}
/**
* i：来到了第几位，值越大，位数越高
* offset:辅助求解nums第i位的数值
* free:为1时，在数值在比nums小的这个条件上，当前位的数值可以随便选，；为0时，在比nums这个数小的条件上,当前位数值不能随便选
* status:位运算，表示那些数字使用过，0表示未使用过，1表示使用过
*/
public int f2(int[] cnts, int nums, int i, int offset, int free, int status) {
if (i == 0) {
return 1;
}
int ans = 0;
//得到当前的数值
int cur = (nums / offset) % 10;
//计算当前位序列字段的循环起始位置，这是为了避免当计算最高位的情况时，取到0这个无效值
int start = status == 0 ? 1 : 0;
if (free == 0) {
for (int p = start; p < cur; p++) {
if ((status & (1 << p)) == 0) {
ans += cnts[i - 1];
}
}
//当选择的值与cur相同时
if (!(status == 0 && cur == 0) && (status & (1 << cur)) == 0) {
ans += f2(cnts, nums, i - 1, offset / 10, 0, (status | (1 << cur)));
}
} else {
ans += cnts[i];
}
return ans;
}
}
}5、至少有1位重复的数字个数
题目描述： 给定正整数 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
解题思路：
第5题时第4题的反例
求解在1-n的范围内至少有一位重复数字的正整数个数
就相当于求解在1-n的范围内所有每位上的数值都不同的正整数的个数
1-n的范围内至少有一位重复数字的正整数个数=n-1-n的范围内所有每位上的数值都不同的正整数的个数
代码如下
package main.java.class084;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_NumbersWithRepeatedDigits
* @description: 至少有1位重复的数字个数
* // 给定正整数n，返回在[1, n]范围内至少有1位重复数字的正整数个数
* // 测试链接 : https://leetcode.cn/problems/numbers-with-repeated-digits/
* @author: zs宝
* @create: 2025-10-11 11:02
* @Version 1.0
**/public class Code05_NumbersWithRepeatedDigits {
class Solution {
public int numDupDigitsAtMostN(int n) {
return n-countSpecialNumbers2(n);
}
//由暴力递归优化而来，用社会的提前打表计算一些情况的数量，从而减少递归的次数
public int countSpecialNumbers2(int nums) {
//先求出这个nums是多少位的
int temp = nums / 10;
int len = 1;
int offset = 1;
while (temp > 0) {
temp /= 10;
len++;
offset *= 10;
}
//计算比nums位数低的数值，且满足每一个数位都是 互不相同 的条件
int ans=0;
for(int i=1,k=10,sum=9;i<len;i++,k--,sum*=k){
ans+=sum;
}
//打表辅助计算，当位数与nums相同时，若从第几位开始在比nums小的条件下可以任意取值时，兼顾每位数不同的要求
//通过数学计算在当前位开始能有多少种可能
//比如 len=4 //则 cnt[4]不计算
//cnt[3]=9*8*7
//cnt[2]=8*7 //cnt[1]=7 //cnt[0]=1表示前缀已经确定，数值已经确定了，只有1种情况
int[]cnts=new int[len];
cnts[0]=1;
for(int i=1,k=10-len+1;i<len;i++,k++){
cnts[i]=cnts[i-1]*k;
}
//现在位数比nums低的已经全部算到了ans中，接下来就只用计算位数以nums相同的情况
return ans+f2(cnts,nums,len,offset,0,0);
}
/**
i：来到了第几位，值越大，位数越高
offset:辅助求解nums第i位的数值
free:为1时，在数值在比nums小的这个条件上，当前位的数值可以随便选，；为0时，在比nums这个数小的条件上,当前位数值不能随便选
status:位运算，表示那些数字使用过，0表示未使用过，1表示使用过
*/
public int f2(int[]cnts,int nums,int i,int offset,int free,int status){
if(i==0){
return 1;
}
int ans=0;
//得到当前的数值
int cur=(nums/offset)%10;
//计算当前位序列字段的循环起始位置，这是为了避免当计算最高位的情况时，取到0这个无效值
int start=status==0?1:0;
if(free==0){
for(int p=start;p<cur;p++){
if((status & (1<<p))==0){
ans+=cnts[i-1];
}
}
//当选择的值与cur相同时
if( !(status==0 && cur==0) && (status & (1<<cur))==0){
ans+=f2(cnts,nums,i-1,offset/10,0,(status | (1<<cur)));
}
}else{
ans+=cnts[i];
}
return ans;
}
}
}